\(C_ 6\)-free bipartite graphs and product representation of squares (Q1356758)

From MaRDI portal
Revision as of 13:13, 27 May 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)
scientific article
Language Label Description Also known as
English
\(C_ 6\)-free bipartite graphs and product representation of squares
scientific article

    Statements

    \(C_ 6\)-free bipartite graphs and product representation of squares (English)
    0 references
    26 October 1997
    0 references
    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.
    0 references
    bipartite graph
    0 references
    0 references

    Identifiers