Forced chord counts in locally three-colourable graphs

Does the local 3-colorability condition in Erdős Problem 1091 force cycles with arbitrarily many chords? A separating family would be K₄-free and 4-chromatic while keeping the number of chords of every cycle uniformly bounded.

Why it matters and what counts as progress

Why it matters: A uniform chord bound in 4-chromatic examples would separate local colorability from forced cycle complexity.

What counts as progress: Construct vertex-critical examples with a universal chord bound or prove a stronger forced-chord conclusion under additional graph assumptions.

How the problem developed

1982 · Theorem [1]
Heinz-Jürgen Voss Proved that every K₄-free graph with chromatic number at least four contains an odd cycle with at least two chords.
8 Apr 2026 · Reported counterexample [2]
Boris Alexeev, Moe Putterman, Mehtaab Sawhney, Mark Sellke and Gregory Valiant Gave locally 3-colourable 4-chromatic K₄-free graphs in which every cycle has at most ten chords, refuting any bound that grows with the local-colourability radius.

AI contribution

Short proofs in combinatorics, probability and number theory II

Boris Alexeev, Moe Putterman, Mehtaab Sawhney, Mark Sellke, Gregory Valiant

For every m≥1, an explicit K₄-free graph on 20m+31 vertices is 4-chromatic and vertex-critical, while every cycle has at most ten chords. This refutes the proposed unbounded forced chord count under the stated local 3-colorability condition.

AI involvementAI-led

ImportanceNotable

Technical verificationFormal (human)

Human understandingFull