Counterexample to a conjecture of Györi on C₂l-free bipartite graphs

DOI10.1016/J.DISC.2006.07.003MaRDI QIDQ868335zbMATH OpenOpenAlexWikidataFDO

Authors C. Balbuena, P. García-Vázquez, Xavier Marcote, J. Carlos Valenzuela-Tripodoro

Publication date 2 March 2007

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2006.07.003

zbMATH Keywords

bipartite graphscyclesforbidden subgraphs

Mathematics Subject Classification ID

Paths and cycles (05C38)

Review text

\textit{E. Györi} [Discrete Math. 165/166, 371--375 (1997; Zbl 0873.05058)] stated the following conjecture: Conjecture~1. If \(G=(X,Y)\) is a bipartite graph with color classes \(X\),\(Y\), where \(| X| =m\), \(| Y| =n\), \(m2\leq n\), \(3\leq l\leq m\) and \(G\) has at least \((l-1)n+m-l+2\) edges, then \(G\) must contain a cycle of length \(2l\). The current note provides a counterexample that disproves Conjecture~1 when \(m\geq 2l-1\). The following reformulation of Conjecture~1 is proposed: Conjecture~2. If \(G=(X,Y)\) is a bipartite graph with color classes \(X\),\(Y\), where \(| X| =m\), \(| Y| =n\), \(m2\leq n\), \(3\leq l\leq m\) such that \(m>(l-1)2\) and \(G\) has at least \((l-1)n+1/(l-1)m2\) edges, then \(G\) must contain a cycle of length \(2l\).

Recommendations

• Four-cycles in graphs without a given even cycle
• scientific article; zbMATH DE number 2186983
• scientific article; zbMATH DE number 1334624
• Exact bipartite Turán numbers of large even cycles
• On long cycles in a 2-connected bipartite graph

Cites work

• \(C_ 6\)-free bipartite graphs and product representation of squares
• On product representation of powers. I
• Triangle-Free Hypergraphs

Cited in

(3)

• Cycles of given lengths in hypergraphs
• A variation of the Erdős-Sós conjecture in bipartite graphs
• Exact bipartite Turán numbers of large even cycles

This page was built for publication: Counterexample to a conjecture of Györi on \(C_{2l}\)-free bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q868335)