Erdős Problem #1091 — Let $G$ be a $K_4$-free graph with chromatic number $4$. Must $G$ contain an odd cycle with at least two diagonals?

Erdős posed the question in 1976: every $K_4$-free graph with chromatic number $4$ should contain an odd cycle with at least two diagonals. The stronger local-colourability formulation asks whether the number of diagonals must become arbitrarily large.

Known results

• Larson, 1979: a $K_4$-free graph with no odd cycle having a diagonal is bipartite, has a cut vertex, or has a vertex of degree at most $2$.
• Voss, 1982: every $K_4$-free $4$-chromatic graph contains an odd cycle with at least two diagonals.
• The pentagonal wheel shows that three diagonals are not always guaranteed.

April 9, 2026 counterexample

Alexeev, Putterman, Sawhney, Sellke, and Valiant give explicit $K_4$-free graphs $G_m$ with $20m+31$ vertices, chromatic number $4$, and every proper subgraph $3$-colourable, indeed $2$-degenerate. Every cycle has at most $10$ chords, so the preprint claims to disprove the proposed function $f(r)\to\infty$; this claim is unverified.

Current status (as of September 2026): Voss’s two-diagonal theorem settles the original question, while the stronger unbounded-diagonal assertion is refuted by an explicit but not independently verified 2026 preprint.