Hadwigers Vermutung

Der K 4 {\displaystyle K_{4}} als Minor eines Graphen, für dessen Färbung k = 4 {\displaystyle k=4} Farben benötigt werden.

In der Graphentheorie stellt die Vermutung von Hadwiger, auch kurz als Hadwiger-Vermutung bezeichnet, einen Zusammenhang zwischen Färbbarkeit von Graphen und dem Vorkommen vollständiger Minoren her. Ihre Aussage ist, dass ein Graph, der keine gültige Färbung mit weniger als k {\displaystyle k} Farben besitzt, einen K k {\displaystyle K_{k}} -Minor hat. In Kurzform: χ ( G ) ≥ k   ⇒   K k ⪯ G {\displaystyle \chi (G)\geq k\ \Rightarrow \ K_{k}\preceq G} . Als Abkürzung wird häufig die Bezeichnung ( H k ) {\displaystyle (H_{k})} verwendet.

Die Vermutung wurde 1943 von Hugo Hadwiger aufgestellt und ist ein offenes Problem der Mathematik. Béla Bollobás, Paul Allen Catlin und Paul Erdős (1980) nannten es „eines der tiefstliegenden ungelösten Probleme der Graphentheorie“.[1]

Die Vermutung ist eng verbunden mit dem Vier-Farben-Satz, der – bei Berücksichtigung des Satzes von Kuratowski und anderer graphentheoretischer Lehrsätze – mit ihr für k = 5 {\displaystyle k=5} , also mit ( H 5 ) {\displaystyle (H_{5})} , äquivalent ist und zugleich die Basis für den bisher einzigen bekannten Beweis von ( H 6 ) {\displaystyle (H_{6})} liefert. Neil Robertson, Paul Seymour und Robin Thomas konnten 1993 nämlich zeigen, dass Hadwigers Vermutung für k = 6 {\displaystyle k=6} ebenfalls mit dem Vier-Farben-Satz äquivalent ist.[2]

Die Vermutung umfasst die Folgerung aus dem 2004 bewiesenen Satz von Robertson-Seymour, dass die Klasse F k {\displaystyle F_{k}} der Graphen, deren Minoren alle k − 1 {\displaystyle k-1} -färbbar sind, durch eine endliche Menge verbotener Minoren charakterisiert ist. Hadwigers Vermutung besagt, dass diese Menge nur den K k {\displaystyle K_{k}} -Minor enthält.

Als Verschärfung der Vermutung von Hadwiger gilt die Hajós-Vermutung, die den K k {\displaystyle K_{k}} nicht als Minor, sondern sogar als topologischen Minor fordert. Diese Vermutung ist für k ≤ 5 {\displaystyle k\leq 5} korrekt, für k = 6 {\displaystyle k=6} offen und für alle größeren k {\displaystyle k} falsch, was jedoch keine Auswirkungen auf die Vermutung von Hadwiger hat.

Stand der Dinge

  • Die Vermutung von Hadwiger ist bislang unbewiesen und es liegen nur Teilresultate vor.
  • Für k = 5 {\displaystyle k=5} ist die Hadwiger-Vermutung mit dem Vier-Farben-Satz äquivalent (Äquivalenzsatz von Wagner) und ebenso für k = 6 {\displaystyle k=6} .[3][2]
  • Für die Fälle k ≤ 6 {\displaystyle k\leq 6} ist sie demnach gezeigt.[4]
  • Aus der Richtigkeit der Teilvermutung ( H n + 1 ) {\displaystyle (H_{n+1})} folgt für jede natürliche Zahl n {\displaystyle n} stets die Richtigkeit der Teilvermutung ( H n ) {\displaystyle (H_{n})} . Die Schwierigkeit nimmt also mit wachsendem Index zu.[5]
  • 1980 zeigten Bela Bollobas, Paul Catlin und Paul Erdős mit probabilistischen Methoden, dass die Vermutung (in einem spezifischen Sinne) für fast jeden Graphen richtig ist.[1][6]
  • 2009 konnten Maria Chudnovsky und Alexandra Ovetsky Fradkin zeigen, dass eine abgeschwächte Version der Hadwiger-Vermutung für die Klasse der Klauen-freien Graphen korrekt ist,[7] womit sie das Ergebnis von Seymour, Robertson und Thomas, dass die Vermutung für alle Kantengraphen korrekt ist, ausweiteten.
  • Dominic van der Zypen konstruierte 2012 einen Graphen H mit chromatischer Zahl ω, aber ohne unendlichen vollständigen Minor. Das zeigt, dass Hadwigers Vermutung im Abzählbar-Unendlichen nicht gilt.[8]
  • Alexander V. Kostochka[9] und Andrew Thomason[10] bewiesen in den 1980er Jahren unabhängig voneinander, dass jeder Graph ohne K k {\displaystyle K_{k}} -Minor den mittleren Grad O ( k log ⁡ k ) {\displaystyle O(k{\sqrt {\log k}})} hat und somit mit O ( k log ⁡ k ) {\displaystyle O(k{\sqrt {\log k}})} Farben färbbar ist. Das Ergebnis wurde später verbessert, insbesondere kündigten Sergey Norin, Zi-Xia Song und Luke Postle eine Verbesserung auf O ( k ( log ⁡ k ) β ) {\displaystyle O(k{(\log k)}^{\beta })} für jedes β > 1 4 {\displaystyle \beta >{\frac {1}{4}}} .[11][12] an. Postle kündigte 2020 eine Verbesserung auf jedes β > 0 {\displaystyle \beta >0} an[13][14] und sogar O ( k ( log ⁡ log ⁡ k ) 6 ) {\displaystyle O(k{(\log \log k)}^{6})} -Färbbarkeit für Graphen ohne K k {\displaystyle K_{k}} -Minor.

Literatur

  • Reinhard Diestel: Graph Theory (= Graduate Texts in Mathematics. Band 173). 3. Auflage. Springer Verlag, Berlin / Heidelberg / New York 2005, ISBN 3-540-26182-6 (MR2159259). 
  • Rudolf Halin: Graphentheorie I (= Erträge der Forschung. Band 138). Wissenschaftliche Buchgesellschaft, Darmstadt 1980, ISBN 3-534-06767-3 (MR0586234). 
  • Klaus Wagner: Graphentheorie (= BI-Hochschultaschenbücher. 248/248a). Bibliographisches Institut, Mannheim (u. a.) 1970, ISBN 3-411-00248-4 (MR0282850). 

Einzelnachweise

  1. ↑ a b B. Bollobás, P. Catlin und P. Erdős: Hadwiger’s conjecture is true for almost every graph. (PDF) In: European Journal on Combinatorics, 1980, 1, S. 195–199.
  2. ↑ a b N. Robertson, P. Seymour, R. Thomas: Hadwiger’s conjecture for K 6 {\displaystyle K_{6}} -free graphs. In: Combinatorica, 1993, 13, S. 279–361 doi:10.1007/BF01202354.
  3. ↑ Rudolf Halin: Graphentheorie I. 1980, S. 268 ff., 274–275
  4. ↑ Reinhard Diestel: Graph Theory. 2005, S. 172–175
  5. ↑ Rudolf Halin: Graphentheorie I. 1980, S. 268 ff., S. 275.
  6. ↑ Dies besagt also nicht, dass ab einem gewissen Index κ 0 {\displaystyle {\kappa }_{0}} die Teilvermutung ( H k ) ( ∀ k ≥ κ 0 ) {\displaystyle (H_{k})\;(\forall k\geq {\kappa }_{0})} richtig sei. Siehe Diskussion:Hadwigers Vermutung!
  7. ↑ Maria Chudnovsky, Alexandra Ovetsky Fradkin: An approximate version of Hadwiger's conjecture for claw-free graphs. In: Journal of Graph Theory. 2009, S. n/a, doi:10.1002/jgt.20425.
  8. ↑ Dominic van der Zypen: Hadwiger's conjecture for graphs with infinite chromatic number, Advancement and Development in Mathematical Sciences, Band 4, 2013, S. 1–4. arxiv:1212.3093 2012.
  9. ↑ A. V. Kostochka, Lower bound of the Hadwiger number for graphs with a given mean degree of vertices, Combinatorica, Band 4, 1984, S. 307–316
  10. ↑ Thomason, An extremal function for contractions of graphs, Math. Proc. Cambridge Phil. Soc., Band 95, 1984, S. 261–265, Abstract
  11. ↑ Noring, Song, Postle, Breaking the degeneracy barrier for coloring graphs with no K t {\displaystyle K_{t}} minor, Arxiv 2019
  12. ↑ Postle, Halfway to Hadwigers conjecture, Arxiv 2019
  13. ↑ Postle, Further progress towards Hadwiger's conjecture, Arxiv 2020
  14. ↑ Postle, An even better Density Increment Theorem and its application to Hadwiger's Conjecture, Arxiv 2020