The Hadwiger conjecture, made by Hugo Hadwiger in 1943, states that any loopless graph with no complete minor on t vertices has chromatic number less than t. It generalizes the four color theorem and is known to hold for t up to 6, but remains one of the most important open problems in graph theory.
Facts
StatementThe Hadwiger conjecture proposes that if a graph has no complete graph on t vertices as a minor, then its chromatic number is less than t. It generalizes the four color theorem to arbitrary graphs. 1 Proposed Year Prize StatusNo prize has been offered for a complete proof. The 1993 proof of the t equals 6 case by Robertson, Seymour and Thomas won the 1994 Fulkerson Prize, awarded for outstanding papers in discrete mathematics. 1 Progress Toward ResolutionHadwiger proved the case t equals 4 himself. Klaus Wagner showed in 1937 that the t equals 5 case is equivalent to the four color theorem. Robertson, Seymour and Thomas proved the t equals 6 case in 1993, also relying on the four color theorem. The conjecture remains open for every t greater than 6. 1 Prize Status
Prize Status (category) Prize Status (category) Classification
Resolution Status Sources
1. Hadwiger Conjecture (Wikipedia)
Wikimedia FoundationLead section
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.
Special cases and partial results section
It follows from their proof that linklessly embeddable graphs, a three-dimensional analogue of planar graphs, have chromatic number at most five.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.