Direkt zum Inhalt

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.

Lesermeinung

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.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnerinhalte