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

Literatur[Bearbeiten | Quelltext 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).