Hadwiger's conjecture relates the chromatic number of a graph to its largest clique minor. The linear relaxation asks whether K_t-minor-free graphs are Ct-colorable for an absolute constant C. The previous best bound was t log^{1/4+o(1)} t.

The proof first colors very small K_t-minor-free graphs, with at most t(log t)^{1/2-ε} vertices, using (4+o(1))t colors. It does this by reducing to graphs with small independence number and using the Reed–Seymour fractional coloring bound. A bootstrap lemma then contracts connected bipartite subgraphs to bound χ(G) by a linear function of the chromatic number of a much smaller minor. Iterating this step extends the vertex range from t(log t)^α to t(log t)^{4α/3}. The proof was found by GPT-6 Astra following the authors' directions, and was formalized in Lean by OpenAI Codex.

There is an absolute constant C such that every K_t-minor-free graph is Ct-colorable. A corollary gives a linear bound in the odd Hadwiger number. The linear list-coloring version remains open.