Lexikon der Mathematik: Hadwiger-Vermutung
sagt aus, daß die chromatische Zahl eines Graphen, der den vollständigen Graphen Kr für ein r ∈ ℕ nicht als Minor (Minor eines Graphen) enthält, höchstens r − 1 beträgt.
Die Hadwiger-Vermutung stammt aus dem Jahr 1943 und ist für r ≤ 6 bewiesen.
Für r = 5 ist sie nach dem sog. Äquivalenzsatz von Wagner zum Vier-Farben-Satz äquivalent.
Für r = 6 wurde sie 1993 von N.Robertson, P.Seymour und R.Thomas mit Hilfe des Vier-Farben-Satzes bewiesen. Für alle größeren Werte von r ist sie eine der bekanntesten offenen Vermutungen der Graphentheorie.
Copyright Springer Verlag GmbH Deutschland 2017
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.