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 |
Created claim: Wikidata QID (P12): Q122973139, #quickstatements; #temporary_batch_1721947978549 |
||
(2 intermediate revisions by 2 users not shown) | |||
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 | |||
Property / cites work | |||
Property / cites work: On product representation of powers. I / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: \(C_ 6\)-free bipartite graphs and product representation of squares / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Triangle-Free Hypergraphs / rank | |||
Normal rank | |||
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