Totalfärbung

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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

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.

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.

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