Hadwiger conjecture

A finite graph is a collection of dots joined by lines. Color the dots so that joined dots have different colors. Five dots A through E joined in a ring need three colors: alternating two colors leaves the last dot with a conflict. Merge neighboring dots A and B, then merge their combined dot with C. The remaining three dots form a triangle, with a line between every pair. Hadwiger’s conjecture asks whether every graph that needs many colors contains an equally large fully connected group after deleting dots or lines and merging along lines.[1]

When connected dots must have different colors, what structure forces the need for more colors? Hadwiger’s conjecture proposes a precise answer for every finite simple undirected graph: a graph needing at least $t$ colors must contain a complete graph on $t$ vertices as a minor. Here vertices are dots, edges are their connections, and a minor permits deleting vertices or edges and contracting edges. A useful equivalent description is $t$ disjoint connected groups of vertices, with an edge between every pair of groups. Contracting each group to one vertex gives $K_t$. With $\chi(G)$ denoting the chromatic number of a graph $G$, the assertion is $$K_t\text{ is not a minor of }G\quad\Longrightarrow\quad\chi(G)\le t-1.$$ In a five-cycle A–B–C–D–E–A, merge A with B, then that group with C. The groups {A,B,C}, {D}, {E} yield a triangle minor; the original five-cycle itself has no triangle and needs three colors.[1]

The predicted coloring bound is proved in selected cases. Weaker bounds do not establish it for every size.[1]

The exact implication is required for every graph and every positive integer $t$. The September 9, 2026 preprint gives a general upper bound with an extra factor that grows, although very slowly, with $t$. It does not remove that factor to reach the proposed $t-1$ colors. Results about the stronger odd-minor variant have additional requirements. A counterexample to a stronger variant need not refute the ordinary conjecture.[1]

A dot with many neighbors need not make coloring difficult: a star can use one color for its center and another for all its outer dots. Neighbor counts alone therefore miss the reason more colors are needed. Compressed, fully connected groups offer a more informative obstruction, including ones spread across many dots rather than visible as a triangle in the original drawing.[1]

The four-color theorem concerns planar graphs, which can be drawn without edges crossing. Hadwiger’s conjecture places coloring in a broader theory based on minors, covering graphs without any planar drawing requirement. The connected-group description matters: an obstruction can occupy many vertices even when no large fully connected group is visible among individual vertices. This connects color compatibility with structure that survives contraction.[1]