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 3-Färbung des Bidiakis-Graphen, eines dreiecksfreien planaren Graphen

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

Grötzsch-Graph: ein nicht-planarer dreiecksfreier Graph, der keine 3-Färbung besitzt

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

(Ein Graph heißt dreiecksfrei, wenn er keinen zum vollständigen Graphen ${\displaystyle 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).