\(C_ 6\)-free bipartite graphs and product representation of squares (Q1356758): Difference between revisions

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.