\(C_ 6\)-free bipartite graphs and product representation of squares
type: Item
instance of: scholarly article
title: \(C_ 6\)-free bipartite graphs and product representation of squares
zbMATH Open document ID: 0873.05058
DOI: 10.1016/S0012-365X(96)00184-7
published in: Discrete Mathematics
publication date: 1997-10-26T00:00:00Z
review text: The paper proves the following theorems. (1) If \(G(X,Y)\) is a bipartite graph with color classes \(X\), \(Y\), so that \(|X|=m\), \(|Y|=n\), \(m^2\leq n\), and \(G\) has at least \((l-1)n+ c(l)m^2\) edges for some constant \(c(l)\), then \(G\) must contain a cycle of length \(2l\). Furthermore, for \(l=3\), \(c(3)=1/2\) suffices, and for \(m=o(\sqrt n)\) the coefficient of \(n\) is the best possible. (2) If \(G(X,Y)\) is a bipartite graph with \(e(G)\) edges and with no cycle of length 6, then there is a subgraph \(G_0\) of \(G\) such that \(G_0\) contains no cycles of length 4 either or has at least \({1\over 2}e(G)+1\) edges.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 11N25
zbMATH DE Number: 1019108
zbMATH Keywords: bipartite graph
author: Ervin Győri
reviewed by: László A. Székely
MaRDI profile type: Publication
cites work: Q3137178
cites work: Some Theorems on Abstract Graphs
cites work: On product representation of powers. I
cites work: On a class of degenerate extremal graph problems
cites work: Cycles in bipartite graphs and an application in number theory
full work available at URL: s0012-365x(96)00184-7
OpenAlex ID: W2021817919
description: scientific article; zbMATH DE number 1019108