Hypergraph Hadwiger conjecture for the chromatic number

From papers

For an integer t2t\geq 2, let h(t)h(t) be the largest chromatic number of a hypergraph with no KtK_t-minor; the paper establishes that this quantity exists. A hypergraph is KtK_t-minor-free if it does not contain KtK_t as a minor, where hypergraph minors are obtained by deleting vertices or hyperedges and contracting hyperedges. Hypergraph Hadwiger conjecture. For every integer t2t\geq 2,

h(t)=32(t1).h(t)=\left\lceil\frac{3}{2}(t-1)\right\rceil.

Equivalently, every KtK_t-minor-free hypergraph HH satisfies

χ(H)32(t1).\chi(H)\leq\left\lceil\frac{3}{2}(t-1)\right\rceil.

The lower bound is attained by complete 33-uniform hypergraphs, so the conjecture would give the exact extremal chromatic number. The conjecture remains open even for K3K_3-minor-free hypergraphs.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Raphael Steiner, “Coloring hypergraphs with excluded minors”, arXiv:2206.13635 (2024).

Solutions 0

No solutions have been posted yet.