Chromatic number of Kₜ-minor-free hypergraphs

Conjecture 2 · arXiv:2206.13635

arXiv Conjecture high confidence— first stated 2024-04-19

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.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Conjecture. For every integer $t\geq 2$ we have $h(t)=\left\lceil\frac{3}{2}(t-1)\right\rceil$. In other words, if a hypergraph $H$ does not contain $K_{t}$ as a minor, then $\chi(H)\leq\left\lceil\frac{3}{2}(t-1)\right\rceil$.

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