Hadwigers Vermutung

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 ${\displaystyle k}$ Farben besitzt, einen ${\displaystyle K_{k}}$-Minor hat. In Kurzform: ${\displaystyle \chi (G)\geq k\ \Rightarrow \ K_{k}\preceq G}$. Als Abkürzung wird häufig die Bezeichnung ${\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“.

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 ${\displaystyle k=5}$, also mit ${\displaystyle (H_{5})}$, äquivalent ist und zugleich die Basis für den bisher einzigen bekannten Beweis von ${\displaystyle (H_{6})}$ liefert. Neil Robertson, Paul Seymour und Robin Thomas konnten 1993 nämlich zeigen, dass Hadwigers Vermutung für ${\displaystyle k=6}$ ebenfalls mit dem Vier-Farben-Satz äquivalent ist.

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

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