imported>HenningFernau am 11. Juni 2024 um 20:53 Uhr

2024-06-11T20:53:20Z

Neue Seite

[[Datei:Hadwiger conjecture.svg|mini|300px|Der <math>K_4</math> als Minor eines Graphen, für dessen Färbung <math>k=4</math> 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 [[Minor (Graphentheorie)|Minoren]] her. Ihre Aussage ist, dass ein Graph, der keine [[gültige Färbung]] mit weniger als <math>k</math> Farben besitzt, einen [[Vollständiger Graph|<math>K_k</math>]]-Minor hat. In Kurzform: <math>\chi(G) \ge k \ \Rightarrow \ K_k \preceq G</math>. Als Abkürzung wird häufig die Bezeichnung <math>(H_k)</math> 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“.<ref name="Bollobás">[[Béla Bollobás|B. Bollobás]], [[Paul Allen Catlin|P. Catlin]] und [[Paul Erdős|P. Erdős]]: [https://www.sciencedirect.com/science/article/pii/S0195669880800011/pdf ''Hadwiger’s conjecture is true for almost every graph.''] (PDF) In: ''European Journal on Combinatorics'', 1980, 1, S. 195–199.</ref>

Die Vermutung ist eng verbunden mit dem [[Vier-Farben-Satz]], der – bei Berücksichtigung des [[Satz von Kuratowski|Satzes von Kuratowski]] und anderer [[graphentheoretisch]]er [[Lehrsatz|Lehrsätze]] – mit ihr für <math>k=5</math>, also mit <math>(H_5)</math>, [[Logische Äquivalenz|äquivalent]] ist und zugleich die Basis für den bisher einzigen bekannten Beweis von <math>(H_6)</math> liefert. [[Neil Robertson (Mathematiker)|Neil Robertson]], [[Paul Seymour (Mathematiker)|Paul Seymour]] und [[Robin Thomas (Mathematiker)|Robin Thomas]] konnten 1993 nämlich zeigen, dass Hadwigers Vermutung für <math>k = 6</math> ebenfalls mit dem Vier-Farben-Satz äquivalent ist.<ref name="NR-PS-RT-1">[[Neil Robertson (Mathematiker)|N. Robertson]], [[Paul Seymour (Mathematiker)|P. Seymour]], [[Robin Thomas (Mathematiker)|R. Thomas]]: ''Hadwiger’s conjecture for <math>K_6</math>-free graphs.'' In: ''[[Combinatorica]]'', 1993, 13, S. 279–361 [[doi:10.1007/BF01202354]].</ref>

Die Vermutung umfasst die Folgerung aus dem 2004 bewiesenen [[Satz von Robertson-Seymour]], dass die Klasse <math>F_k</math> der Graphen, deren Minoren alle <math>k-1</math>-färbbar sind, durch eine endliche Menge verbotener Minoren charakterisiert ist. Hadwigers Vermutung besagt, dass diese Menge nur den <math>K_k</math>-Minor enthält.

Als Verschärfung der Vermutung von Hadwiger gilt die [[Hajós-Vermutung]], die den <math>K_k</math> nicht als [[Minor (Graphentheorie)|Minor]], sondern sogar als [[Topologischer Minor|topologischen Minor]] fordert. Diese Vermutung ist für <math>k \le 5</math> korrekt, für <math>k=6</math> offen und für alle größeren <math>k</math> falsch, was jedoch keine Auswirkungen auf die Vermutung von Hadwiger hat.

== Stand der Dinge ==
* Die Vermutung von Hadwiger ist bislang [[Beweis (Mathematik)|unbewiesen]] und es liegen nur Teilresultate vor.
* Für <math>k = 5</math> ist die Hadwiger-Vermutung mit dem [[Vier-Farben-Satz]] äquivalent (''[[Äquivalenzsatz von Wagner]]'') und ebenso für <math>k = 6</math>.<ref name="RH-1">Rudolf Halin: ''Graphentheorie I.'' 1980, S. 268 ff., 274–275</ref><ref name="NR-PS-RT-1" />
* Für die Fälle <math>k \leq 6</math> ist sie demnach gezeigt.<ref name="RD-1">Reinhard Diestel: ''Graph Theory.'' 2005, S. 172–175</ref>
* Aus der Richtigkeit der Teilvermutung <math>(H_{n+1})</math> folgt für jede [[natürliche Zahl]] <math>n</math> stets die Richtigkeit der Teilvermutung <math>(H_n)</math>. Die Schwierigkeit nimmt also mit wachsendem [[Indexmenge (Mathematik)|Index]] zu.<ref name="RH-2">Rudolf Halin: ''Graphentheorie I.'' 1980, S. 268 ff., S. 275.</ref>
* 1980 zeigten Bela Bollobas, Paul Catlin und Paul Erdős mit [[Probabilistische Methode|probabilistischen Methoden]], dass die Vermutung (in einem spezifischen Sinne) für ''fast jeden Graphen'' richtig ist.<ref name="Bollobás" /><ref>Dies besagt also '''nicht''', dass ab einem gewissen [[Indexmenge (Mathematik)|Index]] <math>{\kappa}_0</math> die Teilvermutung <math>(H_k) \; (\forall k \geq {\kappa}_0)</math> richtig sei. Siehe [[Diskussion:Hadwigers Vermutung]]!</ref>
* 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,<ref>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}}.</ref> 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.<ref>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.</ref>
* Alexander V. Kostochka<ref>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</ref> und Andrew Thomason<ref>Thomason, An extremal function for contractions of graphs, Math. Proc. Cambridge Phil. Soc., Band 95, 1984, S. 261–265, [https://www.cambridge.org/core/journals/mathematical-proceedings-of-the-cambridge-philosophical-society/article/abs/an-extremal-function-for-contractions-of-graphs/F5948FD460B372CB7045EEA018F3774D Abstract ]</ref> bewiesen in den 1980er Jahren unabhängig voneinander, dass jeder Graph ohne <math>K_k</math>-Minor den mittleren Grad <math>O (k \sqrt {\log k})</math> hat und somit mit <math>O (k \sqrt {\log k})</math> Farben färbbar ist. Das Ergebnis wurde später verbessert, insbesondere kündigten Sergey Norin, Zi-Xia Song und Luke Postle eine Verbesserung auf <math>O (k {(\log k )}^{\beta} )</math> für jedes <math>\beta > \frac {1}{4}</math>.<ref>Noring, Song, Postle, Breaking the degeneracy barrier for coloring graphs with no <math>K_t</math>
minor, [https://arxiv.org/abs/1910.09378 Arxiv 2019]</ref><ref>[https://arxiv.org/abs/1911.01491 Postle, Halfway to Hadwigers conjecture], Arxiv 2019</ref> an. Postle kündigte 2020 eine Verbesserung auf jedes <math>\beta >0</math> an<ref>[https://arxiv.org/abs/2006.11798 Postle, Further progress towards Hadwiger's conjecture, Arxiv 2020]</ref><ref>Postle, An even better Density Increment Theorem and its application to Hadwiger's Conjecture, [https://arxiv.org/abs/2006.14945 Arxiv 2020]</ref> und sogar <math>O(k {(\log \log k)}^6)</math>-Färbbarkeit für Graphen ohne <math>K_k</math>-Minor.

== Literatur ==
* {{Literatur
|Autor=[[Reinhard Diestel]]
|Titel=Graph Theory
|TitelErg=
|Reihe=Graduate Texts in Mathematics
|BandReihe=173
|Auflage=3.
|Verlag=Springer Verlag
|Ort=Berlin / Heidelberg / New York
|Online=[http://ams.math.uni-bielefeld.de/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=PC&pg7=ALLF&pg8=ET&review_format=html&s4=Diestel&s5=Graph%20Theory&s6=&s7=&s8=All&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq&r=2&mx-pid=2159259 MR2159259]
|Datum=2005
|ISBN=3-540-26182-6}}
* {{Literatur
|Autor=[[Rudolf Halin]]
|Titel=Graphentheorie I
|Reihe=Erträge der Forschung
|BandReihe=138
|Verlag=Wissenschaftliche Buchgesellschaft
|Ort=Darmstadt
|Datum=1980
|ISBN=3-534-06767-3
|Online=[http://ams.math.uni-bielefeld.de/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=PC&pg7=ALLF&pg8=ET&r=1&review_format=html&s4=Halin&s5=I&s6=&s7=&s8=All&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq MR0586234]}}
* {{Literatur
|Autor=[[Klaus Wagner (Mathematiker)|Klaus Wagner]]
|Titel=Graphentheorie
|TitelErg=
|Reihe=BI-Hochschultaschenbücher
|BandReihe=248/248a
|Verlag=Bibliographisches Institut
|Ort=Mannheim (u. a.)
|Datum=1970
|ISBN=3-411-00248-4
|Online=[http://ams.math.uni-bielefeld.de/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=PC&pg7=ALLF&pg8=ET&review_format=html&s4=Wagner&s5=Graphentheorie&s6=&s7=&s8=All&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq&r=4&mx-pid=282850 MR0282850]}}

== Einzelnachweise ==
<references />

[[Kategorie:Vermutung (Graphentheorie)]]

Hadwigers Vermutung - Versionsgeschichte

imported>HenningFernau am 11. Juni 2024 um 20:53 Uhr