Satz von Grötzsch (Graphentheorie)

In der Graphentheorie, einem Teilgebiet der Mathematik, ist der Satz von Grötzsch ein auf Herbert Grötzsch zurückgehender Satz über die Färbbarkeit von Graphen mit drei Farben.

Färbbarkeit

Eine Färbung ordnet jedem Knoten eines Graphen eine Farbe zu, so dass die Knoten jeder Kante mit jeweils unterschiedlichen Farben gefärbt werden. Man interessiert sich für die minimale Anzahl an Farben, die für die Färbung eines gegebenen Graphen notwendig ist. Der Vier-Farben-Satz besagt, dass sich jeder planare Graph mit vier Farben färben lässt. Der Satz von Grötzsch beantwortet die Frage, welche planaren Graphen sich sogar mit drei Farben färben lassen.

Satz von Grötzsch

Ein dreiecksfreier planarer Graph kann mit drei Farben gefärbt werden.

(Ein Graph heißt dreiecksfrei, wenn er keinen zum vollständigen Graphen $K_{3}$ isomorphen Teilgraphen enthält.)

Literatur

Herbert Grötzsch: Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe 8, 109–120 (1959).

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.