Erdős Problem #1091
Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: solved (not automatically the live result).
Subject areas: chromatic number, graph theory.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
UNACCEPTED DRAFT — mathematical editorial review pending
This material is a provisional, source-qualified manuscript published for line-by-line scrutiny and real HTML/LaTeX testing. It has NOT received separate GCL editorial acceptance or independent mathematical certification. Its presence on this website is not evidence of a solution, reviewed coverage, or final publication.
Review the underlying draft on GitHub.
The question in plain language
How complicated must the odd cycles of a graph be when four colours are needed to colour its vertices, but it contains no complete graph on four vertices?
Erdős Problem #1091 contains two questions. First, must a \(K_4\)‑free graph of chromatic number \(4\) contain an odd cycle with at least two diagonals? A diagonal is an edge joining two nonconsecutive vertices on the chosen cycle.
The stronger question asks whether excluding all small four-chromatic subgraphs forces an odd cycle with an arbitrarily large number of diagonals.
A small example
Take the five-vertex cycle \(C_5\) and join a new central vertex to all five cycle vertices. This is the pentagonal wheel. Its outer odd cycle requires three colours and its hub needs a fourth; it contains no \(K_4\).
Exactly six distinct cycles of length five occur, and direct edge enumeration shows every such cycle has at most two diagonals, with some achieving two. The example explains why replacing “two diagonals” with “three diagonals” fails as a universal assertion. It does not resolve the more demanding condition that every small subgraph be three-colourable.
What is known
The original one-diagonal question was proved by Larson (1979). Voss (1982) proved the stronger two-diagonal assertion.
For the much stronger local-to-global question, the maintained catalogue reports a negative result attributed to an internal OpenAI model, constructing arbitrarily large four-chromatic critical graphs with at most ten diagonals on any cycle. This newer mathematical proof has not been independently audited by GCL, so the statement is recorded as a reported external result rather than a verified new theorem.
GCL's current state
Authenticated source return #2362 distinguishes the affirmative first question from the reported negative second question, and checks the six-vertex wheel exactly.
The original Voss paper and complete recent construction remain pending primary-source proof review.
What remains
Review Larson (1979), Voss (1982) and the reported recent construction, including their diagonal definitions, graph-criticality, local chromatic assumptions and proof of a uniform ten-diagonal bound. A finite pentagonal wheel is not evidence for the asymptotic local-chromatic claim.
Sources and claim boundaries
Erdős Problem #1091, historical and reported newer status; Erdős (1976), p. 4; Larson (1979); Voss (1982); GCL source return #2362. The wheel count is independently checked. The article is unaccepted; the newer theorem is not independently certified.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2362 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.