Hadwinger's guess

The one as a minor of a graph, for the coloring of which colors are required. ${\displaystyle K_{4}}$ ${\displaystyle k=4}$

In graph theory , the presumption of Hadwiger , also abbreviated Hadwiger conjecture refers to a relationship between colorability of graphs and the occurrence of complete minors ago. What you are saying is that a graph that has no valid coloring with less than colors has a -minor. In brief: . The term is often used as an abbreviation . ${\displaystyle k}$ ${\displaystyle K_{k}}$ ${\displaystyle \chi (G)\geq k\ \Rightarrow \ K_{k}\preceq G}$ ${\displaystyle (H_{k})}$

The conjecture was made by Hugo Hadwiger in 1943 and is an open problem in mathematics . Béla Bollobás , Paul Allen Catlin and Paul Erdős (1980) called it "one of the deepest unsolved problems in graph theory".

The conjecture is closely related to the four-color theorem , which - taking into account Kuratowski's theorem and other theorems of graph theory - is equivalent to it for , i.e. with , and at the same time provides the basis for the only known proof of Neil Robertson , Paul Seymour and Robin Thomas were able to show in 1993 that Hadwinger's conjecture for is also equivalent to the four-color theorem. ${\displaystyle k=5}$ ${\displaystyle (H_{5})}$ ${\displaystyle (H_{6})}$ ${\displaystyle k=6}$

The conjecture includes the conclusion from the Robertson-Seymour theorem, proved in 2004 , that the class of graphs whose minors are all -colourable is characterized by a finite set of forbidden minors. Hadwinger's conjecture is that this set only contains the -minor. ${\displaystyle F_{k}}$ ${\displaystyle k-1}$ ${\displaystyle K_{k}}$

As a tightening of Hadwiger 's conjecture , the Hajós conjecture , which does not require the as a minor , but even as a topological minor . This conjecture is correct, open and wrong for all major ones, but this has no effect on Hadwiger's conjecture. ${\displaystyle K_{k}}$ ${\displaystyle k\leq 5}$ ${\displaystyle k=6}$ ${\displaystyle k}$

state of things

• Hadwiger's conjecture has so far not been proven and only partial results are available.
• For the Hadwiger conjecture is equivalent to the four-color theorem ( Wagner's equivalence theorem ) and also for . ${\displaystyle k=5}$ ${\displaystyle k=6}$
• It is therefore shown for the cases . ${\displaystyle k\leq 6}$
• From the correctness of the partial assumption follows for each natural number the accuracy of the partial assumption always . The difficulty increases as the index increases. ${\displaystyle (H_{n+1})}$ ${\displaystyle n}$ ${\displaystyle (H_{n})}$
• In 1980, Bela Bollobas, Paul Catlin, and Paul Erdős used probabilistic methods to show that the conjecture (in a specific sense) is correct for almost every graph .
• In 2009 Maria Chudnovsky and Alexandra Ovetsky Fradkin were able to show that a weakened version of the Hadwiger conjecture is correct for the class of claw-free graphs, thus extending the result of Seymour, Robertsen and Thomas that the conjecture is correct for all edge graphs .
• In 2012 Dominic van der Zypen constructed a graph H with a chromatic number ω, but without an infinite complete minor. This shows that Hadwinger's conjecture in the countable-infinite does not hold.

literature

• Reinhard Diestel : Graph Theory (=  Graduate Texts in Mathematics . Volume 173 ). 3. Edition. Springer Verlag, Berlin / Heidelberg / New York 2005, ISBN 3-540-26182-6 ( MR2159259 ).
• Rudolf Halin : Graph Theory I (=  yields of research . Volume 138 ). Wissenschaftliche Buchgesellschaft, Darmstadt 1980, ISBN 3-534-06767-3 ( MR0586234 ).
• Klaus Wagner : Theory of graphs (=  BI university pocket books. 248 / 248a). Bibliographisches Institut, Mannheim ( inter alia ) 1970, ISBN 3-411-00248-4 ( MR0282850 ).

Individual evidence

1. ↑ ^{a b} B. Bollobás , P. Catlin and P. Erdős : Hadwiger's conjecture is true for almost every graph. (PDF) In: European Journal on Combinatorics , 1980, 1, pp. 195-199.
2. ^ ^{A b} N. Robertson , P. Seymour , R. Thomas : Hadwiger's conjecture for -free graphs. ${\displaystyle K_{6}}$In: Combinatorica , 1993, 13, pp. 279-361 doi: 10.1007 / BF01202354 .
3. ^ Rudolf Halin: Graphentheorie I. 1980, p. 268 ff., 274–275
4. ^ Reinhard Diestel: Graph Theory. 2005, pp. 172-175
5. ↑ Rudolf Halin: Graphentheorie I. 1980, p. 268 ff., P. 275.
6. ↑ This does not mean that the partial presumption is correct above a certain index . See discussion: Hadwinger's Conjecture ! ${\displaystyle {\kappa }_{0}}$ ${\displaystyle (H_{k})\;(\forall k\geq {\kappa }_{0})}$
7. ^ Maria Chudnovsky, Alexandra Ovetsky Fradkin: An approximate version of Hadwiger's conjecture for claw-free graphs. In: Journal of Graph Theory. 2009, p. N / a, doi : 10.1002 / jgt.20425 .
8. ↑ Dominic van der Zypen: arxiv : 1212.3093 2012.