Counterexample to a conjecture of Györi on \(C_{2l}\)-free bipartite graphs (Q868335): Difference between revisions
From MaRDI portal
m rollbackEdits.php mass rollback Tag: Rollback |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.disc.2006.07.003 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2027076080 / rank | |||
Normal rank |
Revision as of 09:35, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Counterexample to a conjecture of Györi on \(C_{2l}\)-free bipartite graphs |
scientific article |
Statements
Counterexample to a conjecture of Györi on \(C_{2l}\)-free bipartite graphs (English)
0 references
2 March 2007
0 references
\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\).
0 references
cycles
0 references
bipartite graphs
0 references
forbidden subgraphs
0 references