Satz von Grötzsch (Graphentheorie)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

Eine 3-Färbung des Bidiakis-Graphen, eines dreiecksfreien planaren Graphen.
Hauptartikel: Färbung (Graphentheorie)

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[Bearbeiten]

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 K_3 isomorphen Teilgraphen enthält.)

Literatur[Bearbeiten]

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).