The Linear List Hadwiger Conjecture
Kawarabayashi and Mohar (2007, Conjecture 1.3) proposed a linear relaxation of Hadwiger's conjecture for list colouring: there is an absolute constant such that every graph with no minor is -choosable. Degeneracy gives ; the best list bounds before this work were superlinear (for example Postle's ), and -minor-free graphs can have list chromatic number close to , so is impossible. Even the ordinary-colouring version, , was open. Is there an absolute constant with for every graph ?
- Result
- Proved(see note)
- Status
- Candidate (review pending)
- AI contribution
- AI-discovered
- Method
- Argument
- Field
- Graph coloring and graph minors
- Posed by
- Ken-ichi Kawarabayashi and Bojan Mohar, A relaxed Hadwiger's conjecture for list colorings, J. Combin. Theory Ser. B 97 (2007), Conjecture 1.3
- Year posed
- 2007
- Years open
- 19y
- Solved
- 2026-09-23
- Model
- Unreleased internal OpenAI model
- Vendor
- OpenAI
- Collaborators
- —
- Verification
- Lean-checked, statement unaudited
- Publication
- Announced
- Collection
- OpenAI math release (October 2026), version adc7f12
- Significance
- 48 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Theorem 1.1: there is an absolute integer such that every finite nonempty simple graph satisfies ; Corollary 1.2 gives the ordinary linear Hadwiger bound . The constant is not computed or optimised and must be at least by Steiner's examples. The proof shows -minor-free graphs on at most vertices are -choosable and then lifts this to all orders through Postle-style separability and a three-district recursion. It does not give close to or .
What the AI did
Produced by an unreleased internal OpenAI model as part of an OpenAI evaluation on open research problems. The release README says the vast majority of results used 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 Riemann zeta zero-free region work and the Hodge conjecture for CM abelian varieties). The manuscript is authored as OpenAI with no human author named. The README also cautions that unformalized results could have issues.
Verification
No independent mathematician has checked this yet. Checked here: the abstract, introduction, Theorem 1.1 and the INPUTS.md file, read against Kawarabayashi-Mohar Conjecture 1.3 as cited. The proof was not refereed. INPUTS.md lists three results used without proof: the Reed-Seymour fractional bound, a connectivity-extraction theorem (Delcourt-Postle, credited to Girao-Narayanan) and a terminal-linkage theorem (Delcourt-Postle, after Bollobas-Thomason), plus LP duality. The manuscript is dated 23 September 2026 but cites work posted 1 October 2026, so the text was revised after its date. Lean-checked on the release's own Comparator challenge ListHadwiger (OAI.LinearListHadwiger.main_theorem) together with its solution module, both present at the pinned commit; the challenge is not listed in the release's formalization catalogue, the statement was read here but not independently audited, and the development was not rebuilt here.