Hadwiger conjecture (graph theory)

Unsolved problem in mathematics:

Does every graph with chromatic number ${\displaystyle k}$ have a ${\displaystyle k}$-vertex complete graph as a minor?

(more unsolved problems in mathematics)

In graph theory, the Hadwiger conjecture states that if ${\displaystyle G}$ is loopless and has no ${\displaystyle K_{t}}$ minor then its chromatic number satisfies ${\displaystyle \chi (G)<t}$. It is known to be true for ${\displaystyle 1\leq t\leq 6}$. The conjecture is a generalization of the four-color theorem and is considered to be one of the most important and challenging open problems in the field.

In more detail, if all proper colorings of an undirected graph ${\displaystyle G}$ use ${\displaystyle k}$ or more colors, then one can find ${\displaystyle k}$ disjoint connected subgraphs of ${\displaystyle G}$ such that each subgraph is connected by an edge to each other subgraph. Contracting the edges within each of these subgraphs so that each subgraph collapses to a single vertex produces a complete graph ${\displaystyle K_{k}}$ on ${\displaystyle k}$ vertices as a minor of ${\displaystyle G}$.

This conjecture, a far-reaching generalization of the four-color problem, was made by Hugo Hadwiger in 1943 and is still unsolved.^[1] Bollobás, Catlin & Erdős (1980) call it "one of the deepest unsolved problems in graph theory."^[2]