SOLVED
This has been resolved in some other way than a proof or disproof.
Let $G$ be a $K_4$-free graph with chromatic number $4$. Must $G$ contain an odd cycle with at least two diagonals?
More generally, is there some $f(r)\to \infty$ such that every graph with chromatic number $4$, in which every subgraph on $\leq r$ vertices has chromatic number $\leq 3$, contains an odd cycle with at least $f(r)$ diagonals?
Erdős originally asked about the existence of just one diagonal, which is true, and was proved by Larson
[La79]. In fact Larson proved the following stronger conjecture of Bollobás and Erdős: if $G$ is a $K_4$-free graph containing no odd cycle with a diagonal then either $G$ is bipartite, or $G$ contains a cut vertex, or $G$ contains a vertex with degree $\leq 2$.
The pentagonal wheel shows that three diagonals are not guaranteed.
The first question was solved in the affirmative by Voss
[Vo82].
An internal OpenAI model (see
[APSSV26b]) has provided a negative answer to the second question: for every $m\geq 1$ there is a graph $G$, with no $K_4$, on $\asymp m$ many vertices with chromatic number $4$, such that every proper subgraph has chromatic number $\leq 3$, and every cycle in $G$ contains at most $10$ diagonals.
View the LaTeX source
This page was last edited 09 April 2026. View history
Additional thanks to: Quanyu Tang
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #1091, https://www.erdosproblems.com/1091, accessed 2026-04-11
