χ_ℓ ≤ 2t for K_t-minor-free graphs
AX_kt_minor_free_list_chromatic_2t
Source: arXiv:2110.09403 — Improved lower bound for the list chromatic number of graphs with no $K_t$ minor
Problem 1 · arXiv:2110.09403
Status open high confidence
The conjecture asks whether the list chromatic number of every $K_t$-minor-free graph is at most $2t$. The source paper itself established the lower bound $(2-o(1))t$, showing that if the conjecture holds the bound $2t$ would be essentially tight. As of 2026, the best known upper bound for $\chi_\ell$ of $K_t$-minor-free graphs remains superlinear in $t$ (of the form $O(t(\log\log t)^6)$), leaving a gap. A follow-up by Fischer and Steiner (2023) generalises the lower bound to all $H$-minor-free graphs but does not resolve the upper bound question.
Cited literature (1)
-
Generalises the $(2-o(1))t$ lower bound from $K_t$-minor-free graphs to all $H$-minor-free graphs (showing $f_\ell(H) \ge (1-\varepsilon)(v(H)+\kappa(H))$ for large $H$), strengthening the source paper's result but not establishing the conjectured upper bound $2t$.
Reviewer notes. The current best upper bound for the list chromatic number of $K_t$-minor-free graphs is $O(t(\log\log t)^6)$, far above the conjectured $2t$. The conjecture is open with high confidence: the source paper is from 2021, a broad web search and Steiner's own research page confirm no proof of the $2t$ upper bound has appeared. The Fischer–Steiner follow-up (arXiv:2304.04246) only improves the lower-bound side.
OpenAI manuscript collection partial progress
OpenAI's manuscript proves the linear bound $\chi_\ell(G) \le C\,h(G)$, so $K_t$-minor-free graphs have list chromatic number $O(t)$. Its constant is not optimised, so the bound $2t$ remains open.
- 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. This is partial progress, so the status above is unchanged.
Context
Having established the lower bound $(2-o(1))t$ for the maximum list chromatic number of $K_t$-minor free graphs, the author asks whether the probabilistic lower-bound construction is essentially optimal up to lower-order terms, or whether the lower bound can be further improved beyond $2t$.
Source paper
Improved lower bound for the list chromatic number of graphs with no $K_t$ minor
Raphael Steiner · 2021-10-18
https://arxiv.org/abs/2110.09403
PDF source