Open problem, Combinatorics and discrete mathematics, posed 1943

Hadwiger's conjecture (graph minors)

Open

Every loopless graph $G$ with no $K_t$ minor is $(t - 1)$ -colorable; equivalently, every graph $G$ with chromatic number $\chi(G) \ge t$ contains the complete graph $K_t$ as a minor.

Research frontier as of 2026

As of 2026, Hadwiger's conjecture is proved for $t \le 6$ and open for all $t \ge 7$ . Even the linear Hadwiger conjecture—that $\chi(G) \le C t$ for every $K_t$ -minor-free graph $G$ —remains open. After Kostochka (1982) and Thomason (1984) showed that degeneracy gives $\chi(G) = O(t \sqrt{\log t})$ , Norin, Postle, and Song (2019/2023) broke the degeneracy barrier, and Delcourt and Postle (2021) established the current best general bound $\chi(G) = O(t \log \log t)$ .

Best known results

Hadwiger's conjecture holds exactly for all $t \le 6$ (Robertson, Seymour, and Thomas, 1993).
Every $K_t$ -minor-free graph $G$ has chromatic number $\chi(G) = O(t \log \log t)$ (Delcourt and Postle, 2021, improving Norin–Postle–Song).

Tools and where they stop

Tool	Achieved	Where it stops
Graph minor structure theory and apex reductions	Classifies minimal $6$ -chromatic $K_6$ -minor-free graphs as apex graphs over planar graphs, reducing $t = 6$ to the four-color theorem.	For $t \ge 7$ , $K_t$ -minor-free graphs can be built from higher-genus surfaces and vortices that are no longer controlled by planar coloring theorems.
Dense subgraph linking and chromatic-separability decompositions	Extracts vertex-disjoint dense highly connected subgraphs in high-chromatic graphs and links them into a $K_t$ minor, yielding $\chi(G) = O(t \log \log t)$ .	Recursive density-increment steps lose a $\log \log t$ factor when balancing small-graph bounds against the number of parts needed to build $K_t$ .

Open questions

Is every graph with no $K_7$ minor $6$ -colorable ( $t = 7$ )?
Does there exist an absolute constant $C > 0$ such that every $K_t$ -minor-free graph $G$ satisfies $\chi(G) \le C t$ (the linear Hadwiger conjecture)?

References

Neil Robertson, Paul Seymour, Robin Thomas (1993). Hadwiger's conjecture for K6-free graphs · DOI:10.1007/BF01202354
Sergey Norin, Luke Postle, Zi-Xia Song (2023). Breaking the degeneracy barrier for coloring graphs with no Kt minor · DOI:10.1016/j.aim.2023.108959 · arXiv:1910.09378