Science Fair Project Encyclopedia
Hadwiger conjecture (graph theory)
In graph theory, the Hadwiger conjecture (or "Hadwiger's conjecture") states that, if the complete graph on k vertices, Kk, 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 Kk, 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 . 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 K5 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 but it remains unsolved for all k > 6.
Some sources define the Hadwiger number h(G) of a graph G to be the size k of the largest complete graph Kk 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 where χ(G) denotes the chromatic number of G.
- Hadwiger, H. (1943). "Über eine Klassifikation der Streckenkomplexe" (German). Vierteljschr. Naturforsch. ges. Zürich 88, 133-143.
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details