Problem Statement
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?
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?
Categories:
Graph Theory Chromatic Number
Progress
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].
Source: erdosproblems.com/1091 | Last verified: January 19, 2026