12 Knotenfärbung
Definition 12.1
- Eine Knotenfärbung eines Graphen \(G = (V, E)\) ist eine Abbildung \(c: V \rightarrow S\) mit \(c(v) \neq c(w)\) für alle \(vw \in E\).
- Die Menge S nennt man die zur verfügung stehende Farben. Eine k-färbung ist eine Knotenfärbung \(c:V \rightarrow \{1,\ldots,k\}\).
- Die kleinste Zahl k wofür es eine k-Färbung gibt, ist die (Knoten-)chromatische Zahl \(\chi(G\)). Also \[\chi(G) = \min \{ k \in \mathbb{N} \mid \exists f: V \to \{1, \ldots, k\} : \forall \{u,v\} \in E: f(u) \neq f(v) \}\]
- Einen Graph G mit \(\chi(G) = k\) nennt man k-chromatisch.
- Ist \(\chi(G) \leq k\), so heißt G k-färbbar.
Bemerkung
- Eine k-Färbung ist eine Knotenpartition in k unabhängige/stabile Mengen.
- Jeder k-partite Graph ist k-knotenfärbbar. Damit
G ist k-partit <= G ist k-färbbar
Beispiel
- \(\chi(\text{Petersen}) = 3.\)
- Für einen bipartiten Graph G ist \(\chi(G) = 2.\)
- \(\chi(K_n) = n.\)
Satz 12.3 (Vierfarbensatz)
Jeder ebene Graph hat eine 4-Färbung.
Der Beweis ist wegen der Komplexität nicht Teil der Vorlesung.
Beispiel
Die Weltkarte als Graph über die Landnachbarschaftsrelation ist zwar nicht planar einbettbar, aber dennoch 4-färbbar, wie folgendes Bild zeigt.
Für die Uneinbettbarkeit betrachte die Landnachbarschaftsrelation der Länder: Turkey (Tu), Georgia (Ge), Armenia (Ar), Azerbaijan (Az), Iran (Ir), Turkmenistan (Tm), Kazakhstan (Ka) und Russland (Ru). Dann ist durch die Kontraktion der Knoten Ir, Tm, Ka, Ru ergibt sich \(K_5\) und damit ist die Nicht-Einbettbarkeit des Landnachbarschaftsgraphen bewiesen.
Satz 12.4 (Fünffarbensatz)
Jeder ebene Graph hat eine 5-Färbung.
Beweis
Beweis verläuft durch Induktion nach \(n = n(G)\).
Sei G ein ebener Graph mit \(n \geq 3\) und m Knoten. Nach Korollar 11.19 (da \(m \leq 3n - 6\)) gilt: \[ d(G) = \frac{2m}{n} \leq \frac{2(3n-6)}{n} < 6 \] Es gibt also einen Knoten \(v \in V(G)\) mit \(d_G(v) \leq 5\). Dann hat \(H := G - v\) nach (IV) eine Knotenfärbung \(c: V(H) \rightarrow \{1,\ldots,5\}\).
1.Fall: Die Nachbarn \(N_G(v)\) sind mit höchstens 4 Farben gefärbt. Dann kann v mit einer 5. Farbe gefärbt werden und ist G 5-färbbar.
2.Fall: Die Nachbarn \(N_G(v)\) sind mit 5 unterschiedlichen Farben gefärbt, also \(N_G(v) = 5\). OBdA können wir die Nachbarn im Uhrzeigersinn numerieren und färben, sodass \(c(v_i) = i\).
Sei jetzt P ein \(v_1-v_3-\)Weg in H. Da der Kreis \(C := v, v_1, P, v_3, v\) die Knoten \(v_2\) und \(v_4\) in G trennt, trennt P die Knoten auch in H (da G ebener Graph). Definiere jetzt die Graphen \[ H_{i,j} := H[c^{-1}(i) \cup c^{-1}(j)] \] für alle \(i, j \in \{1,\ldots, 5 \}\) mit \(i \neq j\) als der von Farben i und j gefärbten Knoten induzierte Untergraph von H.
Angenommen, \(v_1\) liegt in einer anderen Komponente \(C_1\) von \(H_{1,3}\) als \(v_3\). Dann können wir die Farben 1 und 3 in \(C_1\) tauschen. Dann hat v nur noch 4 Farben für Nachbarn verbraucht und kann v die 5. Farbe bekommen.
Also ist \(v_3 \in C_1\) und \(H_{1,3}\) und damit \(H_{1,3}\) enthält ein \(v_1-v_2-\)Weg P. Da P \(v_2\) und \(v_4\) in H trennt, gibt es kein \(v_2-v_4-\)Weg in \(H_{2,4}\) und liegen \(v_2\) und \(v_4\) in unterschiedliche Komponente von \(H_{2,4}\).
Jetzt können wir erneut die Farben tauschen in der Komponente von \(v_2\) (oder \(v_4\)) und v mit den freiwerdende Farbe färben.
Satz 12.4 (Grötsch, 1959)
Jeder ebene Graph, der kein Dreieck enthält, ist 3-färbbar.
Satz 12.5
- Wenn \(G\) eine Clique der Größe \(k\) enthält, werden mindestens \(k\) Farben benötigt, um diese Clique zu färben.
- Jeder Graph lässt sich mithilfe des Greedy-Algorithmus mit einer Farbe mehr als dem maximalen Knotengrad gefärbt werden. \[w(G) \leq \chi(G) \leq \Delta(G) + 1\]
Definition 12.6
Die Degeneriertheit (engl. degeneracy) \(deg(G)\) eines Graphen \(G\) ist das Maximum über allen Teilgraphen H von G von \(\delta(H)\). D.h. \[ \deg(G) := \max_{H \subseteq G} \delta(H) \]
Bemerkung
- A k-degenerate graph is an undirected graph in which every subgraph has at least one vertex of degree at most k.
- The degeneracy of a graph is the smallest value of k for which it is k-degenerate.
- es gibt oft Teilgraphen \(H\neq G\), in denen der kleinste Knotengrad \(\delta(H)\) höher ist als \(\delta(G)\).
Satz 12.7 (Greedy-Algorithmus mit Degenerationsreihenfolge)
Für jeden Graphen \(G\) gilt: \[\chi(G)\le deg(G)+1\]
Beweis
Die Degeneriertheit \(deg(G)\) berechnet man, indem man wiederholt einen Knoten minimalen Grades entfernt und den jeweils neu entstehenden minimalen Grad notiert (siehe Übung).
Algorithmus: Färbt man die Knoten in umgekehrter Reihenfolge des Entfernens, so benötigt man nie mehr als \(deg(G)+1\) Farben.
Satz 12.8
\(G\) vollständig oder Kreis ungerader Länge \(\implies \chi(G) = \Delta(G) + 1\).
Satz 12.9 (Brools, 1941)
Sei \(G\) ein zusammenhängender Graph, der weder vollständig noch ein Kreis ungerader Länge ist. Dann gilt \[\chi(G)\le\Delta(G).\]
Beweis
Zwischenergebnisse:
- \(c(N(v)) = \{1,\ldots,\Delta(G\}\) und insb. \(d_G(v) = \Delta(G)\)
- \(v_i\) und \(v_j\) liegen in der gleichen Komponente \(C_{ij}\) von \(H_{ij}\)
- \(C_{ij}\) ist ein \(v_i-v_j-\)Weg.
Nehme jetzt an, dass \(C_{ij} \cap C_{ik} \neq \{v_i\}\), d.h. es gibt ein \(u \in C_{ij} \cap C_{ik}, u \neq v_i\) mit \(c(u) = i\). Dann hat u zwei Nachbarn der Farbe j und zwei Nachbarn der Farbe k.
Da \(d_H(u) \leq \Delta(G)\), kann u ungefärbt werden und \(v_i\) ebenfalls (und kann v sogar mit i gefärbt werden). Also ist \(\boxed{C_{ij} \cap C_{ik} = \{v_i\}}\).
Nehmen wir jetzt an, dass \(C_{ij} = \{v_i, v_j\} \in E\) für alle \(1 \leq i,j \leq \Delta(G), i \neq j\). Dann gilt \[ N_G(v_i) \supseteq \{v\} \cup \{v_j: j = 1,\ldots,\Delta(G), j \neq i\} \] Da \(d_G(v_i) \leq \Delta(G)\) gilt wohl, dass G vollständig, was Widerspruch ist. Also oBdA ist \(\{v_1, v_2 \notin E\}\) und \(u \in N_H(v_1)\) mit \(c(u) = 2\). Da \(\Delta(G) \geq 3\), gibt es auch \(v_3\) und \(C_{1,3}\) (Kante oder Weg).
Tausche jetzt Farbe 1 und 3 auf \(C_{1,3}: c^\prime\) (keine Ahnung was das bedeutet). Da c eine beliebige \(\Delta(G)\)- Färbung war, gelten weiterhin die Eigenschaften der neuen \(v_i-v_j-\)Wege \(C_{ij}^\prime\), wobei \(v_1^\prime := v_3, v_3^\prime := v_1\). Da \(u \in N(v_3^\prime)\) und \(c^\prime(u) = 2\), gilt \(u \in C_{2,3}\). Aber gleichzeitig liegt u nach immer auf dem Weg \(C_{1,2} ^\prime\), da \(C_{1,2}\) bis auf \(v_1\) nicht umgefärbt wurde, hat \(v_2\) nach der gleichen Nachbarn x mit \(c^\prime(x) = 1\) usw).
Dann gilt aber \(u \in C_{13}^\prime\), was Widerspruchusw.
Sei \(y_0,\ldots,y_k\) eine maximale Folge mit \(y_i \in N(x)\) und \(c_0(xy_i)\) fehlt an \(y_{i-1}\). Wir definieren die Kantenfärbung \(c_i\) für alle Graphen \(G_i := G - xy_i\):
\[ c_i(e) := \begin{cases} c_0\bigl(xy_{j+1}\bigr), & \text{f\"ur }e = xy_j,\; j = 0,\dots,i-1,\\ c_0(e), & \text{sonst.} \end{cases} \]
Die Färbungen sind gültig und die gleiche Farben wie in \(c_0\) fehlen an x. Sei nun \(\beta\) die fehlende Farbe in \(c_0\) an \(y_k\). \(\beta\) fehlt nicht an x, da sonst hätten wir eine \(\delta + 1\)-Färbung von G durch Erweiterung von \(c_k\) in \(G-xy_k\) erzeugen können.
Also gibt es ein \(z \in N(x)\) mit \(c_0(xz) = \beta\). Sollte \(z \neq y_0,\ldots,y_{k-1}\) sein, wäre k nicht maximal. Also \(z \in \{y_0, \ldots, y_{k-1}\}\), sagen wir \(y_i\).
Sei P ein Weg von \(y_k\) nach x in \(G_k\) mit abwechselnd \(\alpha\)- und \(\beta\)-Kanten. Da in x Farbe \(\alpha\) fehlt, muss die letzte Kante eine \(\beta\)-Kante in \(c_k\) sein.
Da \(c_0(xy_i) = \beta\), ist \(c_k(xy_{i-1}) = \beta\). Knoten \(y_i\) ist aber si gewählt, dass \(c_0(xy) = \beta\) an \(y_{i-1}\) in \(c_0\) fehlt, und damit auch in \(c_{i-1}\). Sei jetzt \(P^\prime\) der Weg in \(G_{i-1}\) von \(y_{i-1}\) nach x, angefangen mit \(\alpha\) und abwechselnd \(\alpha\)- und \(\beta\)-Kanten. Da \(c_k\) und \(c_{i-1}\) ausserhalb \(\{xy : j = i, \ldots, k\}\) sich nicht unterscheiden, folgt \(P^\prime\) erst \(P\) bis \(y_k\).
Knoten \(y_k\) ist aber nicht inzident zu einer \(\beta\)-Kante und wir können \(P^\prime\) ümfärben, damit \(\alpha\) und sowohl x als \(y_{i-1}\) in \(c_{i-1}\) fehlt.
Perfekte Graphen
Definition 12.13
Ein Graph G heißt perfekt, wenn für jeden Untergraph \(H \subseteq G\) gilt \[\chi(H) = w(H)\] D.h. seine Cliquenzahl mit seiner chromatischen Zahl übereinstimmt.
Bemerkung: Die triviale untere Schranke von \(w(H)\) Farben stets ausreicht.
\[\chi(C_5) = 3, w(C_5) = 2\]
Satz 12.14
Bipartite Graphen sind perfekt.
Beweis
Wenn \(w(H) = 2\) gilt \(\chi(H) = 2\), da es zwei Farbklassen gibt. Wenn \(w(H) = 1\), gibt es keine Kanten und damit \(\chi(H) = 1\).
Bemerkung
Weitere perfekte Graphen sind Intervallgraphen und chordale Graphen.
Lemma 12.15
Ist G perfekt und \(G^\prime\) aus G durch Knotenverdopplung entstanden, so ist \(G^\prime\) auch perfekt.
Beweis
Beweis verläuft durch Indukton nach \(n := n(G)\).
- Für \(n = 1\) ist \(G^\prime = K_2\) perfekt.
- Sei nun \(n \geq 2\) und G nicht trivial (\(m 0\)):
Sei \(x \in V(G)\) und \(x^\prime \in V(G^\prime)\) den verdoppelten Knoten von x. Jeder echte Untergraph von \(G^\prime\) ist entweder einen Untergraphen H von G oder einen „Untergraphen mit verdoppelten Knoten“ \(H^\prime\), wofür nach (IV) \(w(H^\prime) = \chi(H^\prime)\) gilt. Also bleibt zu zeigen, dass \(\chi(G^\prime) \leq w(G^\prime)\).
Sei \(w := w(G)\). Dann ist \(w(G^\prime) \in \{w, w+ 1\}\). - Ist \(w(G^\prime) = w + 1\) (also \(x^\prime\) ist Teil einer Clique \(K_{w+1}\)), so gilt \[ \chi(G^\prime) \leq \chi(G) + 1 = w + 1 = w(G^\prime) \] - Ist \(w(G^\prime) = w\), dann ist x kein Teil einer Clique \(K_w\). Sei \[ X := \{v \in V(G): c(v) = c(x)\} \] für eine \(\chi(G)\)-Färbung von G. Da \(\chi(G) = w(G)\) , enthält jeder \(K_w \subseteq G\) ein Knoten aus X. Sei \(H := G - (X - \{x\})\), d.h. in H gibt es keine Clique der Größe w. Da G perfekt ist, kann H mit \(w(H) = w - 1\) Farben gefärbt werden. Da \(x^\prime\) eine Verdopplung von x ist, ist \(X - (\{x\} \cup \{x^\prime\})\) eine stabile Menge in \(G^\prime\) und \(G^\prime - (X - (\{x\} \cup \{x^\prime\})) = H\). Wir können also \(G^\prime\) mit w Farben färben.
Satz 12.16 (Weak Perfect Graph Theorem: Lovàsz, 1972)
Ein Graph \(G\) ist genau dann perfekt, wenn sein Komplement \(\bar{G}\) perfekt ist.
Ohne Beweis.
Satz 12.17 (Strong Perfect Graph Theorem: Chudnovski, Robertson, Seymair & Thomas, 2002)
Ein Graph G ist genau dann perfekt, wenn weder G noch \(\bar{G}\) einen ungerader Kreis der Länge \(\geq 5\) als Untergraphen enthält.