OPEN
This is open, and cannot be resolved with a finite computation.
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].
View the LaTeX source
This page was last edited 06 December 2025.
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-01-16
