Conjecture of Hadwiger

In Graph theory, the conjecture of Hadwiger is a very general conjecture about the problems of Coloration of graph S. Formulée in 1943 by Hugo Hadwiger, it states that if the complete Graphe with K tops, noted $K_k$ , is not a minor of a graph $G$ , then it is possible to color the tops of $G$ with $k-1$ colors.

Hadwiger proved the cases $k \ Leq 4$ in the same article which formulates the conjecture. Wagner proved in 1937 that the case $k=5$ is equivalent to the Théorème of the four colors, and the demonstration in 1976 by Happel and Aken of the theorem of the four colors thus proved at the same time the conjecture of Hadwiger for the case $k=5$ .

In 1993, Robertson, Seymour, and Thomas proved that the case $k=6$ could also be reduced to the theorem of the four colors. This new result led them to check the proof of the theorem of the four colors, and finally to simplify it.

The conjecture of Hadwiger remains open for $k > 6$ .

Reference

Robertson, Neil; Seymour, Paul; Thomas, Robin (1993). " Hadwiger' S conjectures for $K_6$ -free graphs". Combinatorica 14 , 279-361.

Random links: