Chromatic number of Kₜ-minor-free hypergraphs
AX_kt_minor_free_hypergraph_chromatic_bound
Source: arXiv:2206.13635 — Coloring hypergraphs with excluded minors
Conjecture 2 · arXiv:2206.13635
Status open high confidence
Conjecture 2 of Steiner (arXiv:2206.13635) — that h(t) = ⌈3/2(t-1)⌉ for all t ≥ 2 — remains open as of 2026. The paper establishes the matching lower bound by construction and proves the conjecture for hypergraphs with independence number at most 2; the best general upper bound is h(t) = O(t log log t) via Delcourt–Postle. Even the t=3 case (asking whether every K_3-minor-free hypergraph is 3-colorable) is open, with a gap between the lower bound of 3 and the best known upper bound of 4. No follow-up paper resolving the full conjecture was found in a wide literature search.
Reviewer notes. The paper was first posted June 2022 and published in European Journal of Combinatorics in 2024 (ScienceDirect doi:10.1016/j.ejc.2024.…). The conjecture is proven for the special case of hypergraphs with independence number ≤ 2, and for t ∈ {2,3,4,5,6} the bound χ(H) ≤ 2t-2 holds. The t=3 case (Problem 1 in the paper) is the most immediate open question. No citing paper resolving the conjecture was found.
OpenAI manuscript collection partial progress
Combined with the source paper's bound $h(t) \le 2g(t)$, OpenAI's linear bound for graphs gives $h(t) = O(t)$; the conjectured value $\lceil\frac32(t-1)\rceil$ remains open.
Why it applies. The source paper proves $h(t) \le 2g(t)$, where $g(t)$ is the largest chromatic number of a $K_t$-minor-free graph, and the manuscript's corollary $\chi(G) \le C\,h(G)$ gives $g(t) \le C(t-1)$.
- 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
The function $h(t)$ is the smallest integer such that every $K_t$-minor-free hypergraph is $h(t)$-colorable. The paper proves the lower bound $h(t)\geq\left\lceil\frac{3}{2}(t-1)\right\rceil$ by an explicit construction, and conjectures this lower bound is tight. The conjecture remains open even for $t=3$, where the best known upper bound is $4$.
Source paper
Coloring hypergraphs with excluded minors
Raphael Steiner · 2024-04-19
https://arxiv.org/abs/2206.13635