The Alon-Krivelevich-Sudakov conjecture: graphs with a fixed forbidden subgraph have chromatic number O(Delta/log Delta)
Every graph of maximum degree has . Johansson (1996) proved for triangle-free graphs, and Alon, Krivelevich and Sudakov (1999) extended this to graphs with sparse neighborhoods. For general fixed , and already for , the best bounds carried an extra factor. Alon, Krivelevich and Sudakov (1999, Conjecture 3.1) conjectured: for every fixed graph there is such that every -free graph of maximum degree has chromatic number at most . Is this true?
- Result
- Proved(see note)
- Status
- Candidate (review pending)
- AI contribution
- AI-discovered
- Method
- Argument
- Field
- Graph coloring: sparse and F-free graphs
- Posed by
- N. Alon, M. Krivelevich and B. Sudakov, Coloring graphs with sparse neighborhoods, J. Combin. Theory Ser. B 77 (1999), Conjecture 3.1
- Year posed
- 1999
- Years open
- 27y
- Solved
- 2026-10-05
- Model
- Unreleased internal OpenAI model
- Vendor
- OpenAI
- Collaborators
- —
- Verification
- Unreviewed
- Publication
- Announced
- Collection
- OpenAI math release (October 2026), version adc7f12
- Significance
- 42 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Theorem 1.1: for every there are and such that every -free graph of maximum degree has correspondence (DP) chromatic number at most ; Corollary 1.2 gives the same for any fixed forbidden subgraph , which implies the conjecture for ordinary and list coloring. The proof is a round-based random partial coloring with weighted lists, controlled by an entropy potential and local adjustments that offset triangle correlations. Constants and thresholds are not optimized; no explicit leading constant is claimed.
What the AI did
The OpenAI math release (github.com/openai/math, commit adc7f12) states that its results were produced by an unreleased internal OpenAI model under one fixed procedure, averaging about three hours of ChatGPT Pro thinking compute per result. This result is not among the README's stated exceptions (the Re(s) > 11/12 zero-free region write-up and the Hodge conjecture for CM abelian varieties). The manuscript is credited to OpenAI alone and names no human author. The manuscript states that it develops the multiplier and entropy-splitting methods of its companion on the AEKS independence conjecture (25 September 2026) and proves all ingredients itself.
Verification
No independent mathematician has checked this yet. Checked here: the abstract, introduction, Theorem 1.1 and Corollary 1.2 of the TeX source, read against Conjecture 3.1 of Alon, Krivelevich and Sudakov as the manuscript cites it; the proof was not refereed. The family's Lean material (lean/docs/184.md) formalizes only the companion independence bound, not this coloring theorem, so this entry is unreviewed.