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 Farben besitzt, einen -Minor hat. In Kurzform: . Als Abkürzung wird häufig die Bezeichnung verwendet.
Die Vermutung umfasst die Folgerung aus dem 2004 bewiesenen Satz von Robertson-Seymour, dass die Klasse der Graphen, deren Minoren alle -färbbar sind, durch eine endliche Menge verbotener Minoren charakterisiert ist. Hadwigers Vermutung besagt, dass diese Menge nur den -Minor enthält.
Als Verschärfung der Vermutung von Hadwiger gilt die Hajós-Vermutung, die den nicht als Minor, sondern sogar als topologischen Minor fordert. Diese Vermutung ist für korrekt, für offen und für alle größeren falsch, was jedoch keine Auswirkungen auf die Vermutung von Hadwiger hat.
Die Vermutung von Hadwiger ist bislang unbewiesen und es liegen nur Teilresultate vor.
Aus der Richtigkeit der Teilvermutung folgt für jede natürliche Zahl stets die Richtigkeit der Teilvermutung . 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 GraphenH 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 -Minor den mittleren Grad hat und somit mit Farben färbbar ist. Das Ergebnis wurde später verbessert, insbesondere kündigten Sergey Norin, Zi-Xia Song und Luke Postle eine Verbesserung auf für jedes .[11][12] an. Postle kündigte 2020 eine Verbesserung auf jedes an[13][14] und sogar -Färbbarkeit für Graphen ohne -Minor.
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.
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.