Hadwiger conjecture (graph theory)

In graph theory, the conjecture of Hadwiger establishes a link between colorability of graphs and the occurrence of complete minors. Their statement is that a graph has no valid color less than colors has a Minor. In short form: . As a shortcut, the term is often used.

The conjecture generalizes the four- color theorem, which implies together with the set of Kuratowski the statement for. Also, for the only evidence so far is based on the assumption of the validity of the four- color theorem. The assumption was erected in 1943 by Hugo Hadwiger and is an open problem in mathematics. Béla Bollobás, Catlin and Paul Allen Paul Erdős (1980 ) called it "one of the most profound unsolved problems in graph theory ."

The assumption exacerbates the consequence of the 2004 theorem of Robertson - Seymour, that the class of graphs whose minors are all colorable, is characterized by a finite set of forbidden minors. Hadwigers conjecture states that this amount only includes the minor. Neil Robertson, Paul Seymour and Robin Thomas could prove 1993 Hadwigers presumption.

When tightening the conjecture of Hadwiger applies the Hajos conjecture, which asks the not as a minor, but even as a topological minor. This conjecture is false for correct, for open and for all larger, but this has no effect on the conjecture of Hadwiger.

State of affairs

The conjecture of Hadwiger is - as I said - not yet fully proven. For those cases it is easy to show. In the event there is a bit more demanding and for the proof is already quite long.

It is clear that the presumption either for all is correct, or a greatest exists, so that they, and all is correct for all the wrong.

For all the conjecture implies the four- color theorem.

1980 showed Bela Bollobás, Paul Catlin and Paul Erdős with the probabilistic method is that the conjecture is correct for almost all graphs.

2009 were Maria Chudnovsky and Alexandra Ovetsky Fradkin show that the Hadwiger's conjecture for the class of claw - free graph is correct, so they widened the result of Seymour and Thomas Robertsen that the guess is correct for all edges graphs.

Dominic van der Zypen constructed in 2012 a graph H with chromatic number ω, but without infinite complete Minor. This shows that Hadwigers presumption shall not apply in - denumerable infinity.