Status
On this page
Status
Topics
Status
On this page
Status
Topics
Let be a -free graph with chromatic number . Must contain an odd cycle with at least two diagonals?
More generally, is there some such that every graph with chromatic number , in which every subgraph on vertices has chromatic number , contains an odd cycle with at least diagonals?
Source: erdosproblems.com/1091
An accepted solution exists. Settled in another form, for example when its parts resolve differently or the question is open-ended.
The site labels the problem solved, with the two questions answered in opposite directions. The first question, whether a -free graph of chromatic number has an odd cycle with at least two diagonals, is answered yes by the accepted partial claim Voss's two-chord theorem; the second, whether some diagonals are forced by local -colorability, is answered no by the accepted partial claim the ten-chord construction of Alexeev, Putterman, Sawhney, Sellke and Valiant. The two claims together settle both parts of the problem, one yes and one no, so the problem is solved with the mixed value answered.