Counterexample to a conjecture of Györi on \(C_{2l}\)-free bipartite graphs (Q868335): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Created claim: Wikidata QID (P12): Q122973139, #quickstatements; #temporary_batch_1721947978549 |
||
Property / Wikidata QID | |||
Property / Wikidata QID: Q122973139 / rank | |||
Normal rank |
Latest revision as of 00:54, 26 July 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