Totalfärbung

Die Totalfärbung ist ein Begriff aus der Graphentheorie und eine Verallgemeinerung sowohl von der Kantenfärbung als auch von der Knotenfärbung.

Definition

Sei $G=(V,E)$ ein Graph und $c:V\cup E\to \{1,\dots ,k\}$ eine Abbildung, welche jeder Kante und jedem Knoten eine natürliche Zahl (in diesem Zusammenhang auch Farbe genannt) zuordnet. $c$ heißt eine gültige Totalfärbung oder gültige k-Totalfärbung wenn $c(i)\ne c(j)$ für alle adjazenten oder inzidenten Elemente aus $V\cup E$ gilt. Insbesondere wird der Graph also sowohl kanten- als auch knotengefärbt, wobei wieder gefordert wird, dass benachbarte Elemente unterschiedliche Farben erhalten. Dazu kommt die Förderung, dass eine Kante anders gefärbt ist als ihre Endpunkte.

Besitzt ein Graph eine gültige $k$-Totalfärbung, aber keine gültige $(k-1)$-Totalfärbung, so heißt $k$ die totalchromatische Zahl von $G$ und wird mit ${\chi }_T$ bezeichnet.

Beispiel

Eine Totalfärbung des $K_4$ (des vollständigen Graphen mit 4 Knoten)

Der rechts abgebildete Graph ist mit einer gültigen Totalfärbung versehen, da jede eingefärbte Kante oder Knoten nie mit einer Kante oder einem Knoten derselben Farbe benachbart ist. Die Färbung benutzt zwar fünf verschiedene Farben, aber um die totalchromatische Zahl zu bestimmen, müsste erst gezeigt werden, dass es keine gültige Totalfärbung gibt, welche mit weniger Farben auskommt.

Eigenschaften

• Für jeden Graphen gilt offensichtlich $\mathrm{\Delta }(G)+1\le {\chi }_T(G)\le {\chi }^{\prime }(G)+\chi (G)$, wobei $\mathrm{\Delta }(G)$ der Maximalgrad ist, ${\chi }^{\prime }(G)$ der chromatische Index und $\chi (G)$ die chromatische Zahl ist.
• Gilt ${\chi }_T(G)={\chi }^{\prime }(G)+\chi (G)$, so ist $G$ notwendigerweise bipartit.
• Es wird vermutet, dass für einfache Graphen ${\chi }_T(G)\le \mathrm{\Delta }(G)+2$ gilt (Totalfärbungsvermutung). Dies konnte bisher jedoch nur für eingeschränkte Graphklassen gezeigt werden, zum Beispiel für bipartite Graphen.

Literatur

• Lutz Volkmann: Fundamente der Graphentheorie, Springer (Wien) 1996, ISBN 3-211-82774-9 (neuere, Online-Version „Graphen an allen Ecken und Kanten“; PDF; 3,7 MB)