Totalfärbung

Begriff aus der Graphentheorie

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

Definition

Bearbeiten

Sei   ein Graph und   eine Abbildung, welche jeder Kante und jedem Knoten eine natürliche Zahl (in diesem Zusammenhang auch Farbe genannt) zuordnet.   heißt eine gültige Totalfärbung oder gültige k-Totalfärbung wenn   für alle adjazenten oder inzidenten Elemente aus   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  -Totalfärbung, aber keine gültige  -Totalfärbung, so heißt   die totalchromatische Zahl von   und wird mit   bezeichnet.

Beispiel

Bearbeiten
 
Eine Totalfärbung des   (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

Bearbeiten
  • Für jeden Graphen gilt offensichtlich  , wobei   der Maximalgrad ist,   der chromatische Index und   die chromatische Zahl ist.
  • Gilt  , so ist   notwendigerweise bipartit.
  • Es wird vermutet, dass für einfache Graphen   gilt (Totalfärbungsvermutung). Dies konnte bisher jedoch nur für eingeschränkte Graphklassen gezeigt werden, zum Beispiel für bipartite Graphen.

Literatur

Bearbeiten