List Hadwiger Conjecture
OPG_hadwiger_list_kt_minor_free_choosable
Status ai-proved high confidence
OpenAI's manuscript proves $\chi_\ell(G) \le C\,h(G)$ for an absolute constant $C$, where $h(G)$ is the largest order of a clique minor, so every $K_t$-minor-free graph is $Ct$-list-colourable. The constant is not optimised; Steiner's examples force $C \ge 2$.
Cited literature (4)
-
Every $K_t$-minor-free graph is $O(t(\log t)^\beta)$-list-colorable for every $\beta > 1/4$, improving the previous $O(t\sqrt{\log t})$ upper bound and providing the best known bound for list coloring.
-
The maximum list chromatic number of $K_t$-minor-free graphs is at least $(2-o(1))t$, showing $c \geq 2$ is necessary and disproving the specific conjecture of Kawarabayashi–Mohar that $c = 3/2$ suffices.
-
Introduces a λ-choosability framework and proves that for any $\varepsilon > 0$ and sufficiently large $t$, for any partition $\lambda$ of $\lfloor(2-\varepsilon)t\rfloor$, there exists a $K_t$-minor-free graph that is not λ-choosable, showing fundamental limitations on list colorability below the $2t$ threshold.
-
Disproves this conjecture by showing that the maximum list chromatic number of $K_t$-minor free graphs is at least $(2-o(1))t$, which strictly exceeds $\frac{3}{2}t$ for all sufficiently large $t$.
Reviewer notes. Literature status before this model-generated claim: partial. The conjecture that every $K_t$-minor-free graph is $ct$-list-colourable for some absolute constant $c$ remains open. Norin and Postle (2020) established the best current upper bound of $O(t(\log t)^\beta)$-list-colorability for every $\beta > 1/4$, falling short of the conjectured linear bound. Steiner (2022) improved the lower bound to $(2-o(1))t$, refuting the specific sub-conjecture $c = 3/2$ of Kawarabayashi and Mohar and showing $c \geq 2$ is necessary.
OpenAI manuscript collection ai-proved
- A linear list-coloring bound in terms of the Hadwiger number — main result formalized in Lean by OpenAI
Family 157: Graph coloring, clique minors, and Colin de Verdière invariants · Lean formalization scope
These manuscripts were produced by an unreleased OpenAI model and released on
2026-10-06 in github.com/openai/math.
They have not been peer reviewed. Lean formalizations are OpenAI's own and cover
only the scope stated on their scope page; this project has not run or reviewed them.
The status above records the claim; before it, the literature review rated this
entry partial. Its confidence rates
whether the manuscript's theorem settles this entry, not whether the manuscript
is correct.
Discussion
Hadwiger's conjecture asserts that every $ K_t $ - minor -free graph is $ (t − 1) $ -colourable. Robertson, Seymour and Thomas [RST] proved Hadwiger's conjecture for $ t \leq 6 $ . It remains open for $ t \geq 7 $ . In fact, it is open whether every $ K_t $ -minor-free graph is $ ct $ -colourable for some constant $ c\geq 1 $ . It is natural to consider analogous problems for list colourings . First, consider planar graphs. While every planar graph is 4-colourable, Erdös, Rubin and Taylor. [ERT] conjectured that some planar graph is not 4-list-colourable, and that every planar graph is 5-list-colourable. The first conjecture was verified by Voigt [V] and the second by Thomassen [T]. More generally, Borowiecki [B] asked whether every $ K_t $ -minor-free graph is $ (t − 1) $ -list-colourable, which is true for $ t \leq 4 $ but false for $ t = 5 $ by Voigt’s example. Kawarabayashi and Mohar [KM] proposed the stated conjecture, and suggested it might be true with $ c=\frac{3}{2} $ . Barát, Joret and Wood [BJW] proved that $ c\geq\frac{4}{3} $ . In particular, they constructed a $ K_{3t+2} $ -minor-free graph that is not $ 4t $ -list-colourable.
Bibliography
-
[B]Mieczyslaw Borowiecki. Research problem 172 . Discrete Math., 121:235–236, 1993. . Research problem 172 -
[BJW]Janos Barát, Gwenael Joret, David R. Wood. Disproof of the List Hadwiger Conjecture , Electronic J. Combinatorics 18:P232, 2011. Disproof of the List Hadwiger Conjecture -
[ERT]Paul Erdo ̋s, Arthur L. Rubin, and Herbert Taylor. Choosability in graphs . In Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, vol. XXVI of Congress. Numer., pp. 125–157. Utilitas Math., 1980. MathSciNet . Choosability in graphs · MathSciNet -
★
[KM]Ken-ichi Kawarabayashi and Bojan Mohar. A relaxed Hadwiger’s conjecture for list colorings . J. Combin. Theory Ser. B, 97(4):647–651, 2007. MathSciNet . A relaxed Hadwiger’s conjecture for list colorings · MathSciNet -
[RST]Neil Robertson, Paul D. Seymour, and Robin Thomas. Hadwiger’s conjecture for $ K_6 $ -free graphs . Combinatorica, 13(3):279–361, 1993. MathSciNet . Hadwiger’s conjecture for -free graphs · MathSciNet -
[T]Carsten Thomassen. Every planar graph is 5-choosable . J. Combin. Theory Ser. B, 62(1):180–181, 1994. MathSciNet . Every planar graph is 5-choosable · MathSciNet