Math Conjectures

Hadwiger's Conjecture

OPENLandmarkConjectureProposed 1943 · Full conjecture

Canonical statement

Let χ(G)\chi(G) be the chromatic number of a finite simple graph GG, and let KqK_q denote the complete graph on qq vertices. Then GG contains Kχ(G)K_{\chi(G)} as a minor; equivalently, V(G)V(G) has χ(G)\chi(G) pairwise-disjoint nonempty connected branch sets with at least one edge between every two branch sets.
View source LaTeX
Let \(\chi(G)\) be the chromatic number of a finite simple
graph \(G\), and let \(K_q\) denote the complete graph on \(q\) vertices.
Then \(G\) contains \(K_{\chi(G)}\) as a minor; equivalently, \(V(G)\) has
\(\chi(G)\) pairwise-disjoint nonempty connected branch sets with at least
one edge between every two branch sets.
GRAPH-001:[Hadwiger1943][Seymour2016Hadwiger][NorineEtAl2026Hadwiger]
Graph theoryCombinatorics

Notes

Hadwiger conjectured in 1943 that every finite graph GG contains the complete graph Kχ(G)K_{\chi(G)} as a minor, where χ(G)\chi(G) is the chromatic number; equivalently, the vertex set can be partitioned into χ(G)\chi(G) connected branch sets with an edge between every two of them [Hadwiger1943]. Since the case χ(G)=5\chi(G)=5 already implies the Four-Color Theorem for planar graphs, the conjecture is widely regarded as one of the deepest open problems in graph theory.

The statement is proved for all graphs with chromatic number at most 66; the cases 55 and 66 both rest on the Four-Color Theorem. Seymour's survey gives a thorough account of these results and of the surrounding partial and asymptotic work [Seymour2016Hadwiger]. On the quantitative side, it has long been known that graphs with no KtK_t minor can be colored with O(tlog⁡t)O(t\sqrt{\log t}) colors, a bound coming from degeneracy; Norin, Postle, and Song broke this barrier, obtaining colorings with o(tlog⁡t)o(t\sqrt{\log t}) colors [NorineEtAl2026Hadwiger].

The full conjecture remains open for every chromatic number at least 77.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.