Hadwiger conjecture (graph theory)

From Wikipedia, the free encyclopedia

In graph theory, the Hadwiger conjecture (or "Hadwiger's conjecture") states that, if the complete graph on $k$ vertices, $K k$ , is not a minor of a graph $G$ , then $G$ has a vertex coloring with $k - 1$ colors. Equivalently, if there is no sequence of edge contractions (each identifying the two endpoints of an edge) that brings graph $G$ to the complete graph $K k$ , then $G$ has a vertex coloring with $k - 1$ colors.

This conjecture was made by Hugo Hadwiger in 1943. In the same paper, Hadwiger proved the conjecture for $k \leq 4$ . Wagner proved in 1937 that the case $k = 5$ is equivalent to the four color theorem and therefore we now know it to be true. (Note that the case $k = 5$ easily implies the four color theorem because $K 5$ is not a minor of any planar graph.) Robertson, Seymour, and Thomas (1993) proved Hadwiger's conjecture for $k = 6$ , also using the four color theorem. Thus the conjecture is true for $k \leq 6$ but it remains unsolved for all $k > 6$ .

[edit] Hadwiger number

Some sources define the Hadwiger number $h (G)$ of a graph $G$ to be the size $k$ of the largest complete graph $K k$ that is a minor of $G$ (or equivalently can be obtained by contracting $G$ ). Then the Hadwiger conjecture can be stated in the simple algebraic form $\chi(G) \leq h(G)$ where $χ(G)$ denotes the chromatic number of $G$ .