Begriff aus der Graphentheorie.

Eine Totalfärbung eines GraphenG mit der Eckenmenge E(G) und der Kantenmenge K(G) ist eine Abbildung \begin{eqnarray}h:E(G)\cup K(G)\to \{1,2,\ldots,k\}\end{eqnarray} so, daß h(x) ≠ h(y) für alle adjazenten oder inzidenten Elemente x, y ∈ E(G) ∪ K(G) gilt. Man spricht dann auch von einer k-Totalfärbung. Besitzt G eine k-Totalfärbung, aber keine (k − 1)-Totalfärbung, so nennt man k totalchromatische Zahl von G, in Zeichen \begin{eqnarray}k={\chi}_{T}(G).\end{eqnarray}

Für jeden Graphen G ergibt sich unmittelbar aus der Definition der totalchromatischen Zahl die Ungleichungskette \begin{eqnarray}{\rm{\Delta}}(G)+1\le {\chi}_{T}(G)\le \chi (G)+{\chi}^{\prime}(G),\end{eqnarray} wobei Δ(G) der Maximalgrad, χ(G) die chromatische Zahl und χ′(G) der chromatische Index ist. Im Jahre 1967 bemerkten M. Behzad, G. Chartrand und J.K. Cooper Jr., daß die Gleichheit \begin{eqnarray}{\chi}_{T}(G)=\chi (G)+{\chi}^{\prime}(G)\end{eqnarray} höchstens bei bipartiten Graphen eintritt. Ist G ein beliebiger Graph, so kann man ohne große Mühe \begin{eqnarray}{\chi}_{T}(G)\le 2{\rm{\Delta}}(G)+1\end{eqnarray} nachweisen. Jedoch haben V.G. Vizing 1964 und M. Behzad 1965 unabhängig voneinander vermutet, daß für die totalchromatische Zahl sogar die viel bessere Abschätzung \begin{eqnarray}{\chi}_{T}(G)\le {\rm{\Delta}}(G)+2\end{eqnarray} gültig ist. Diese Ungleichung ist inzwischen als Totalfärbungs-Vermutung von Behzad und Vizing in die Literatur eingegangen. Trotz aller Anstrengungen ist man von einem vollständigen Beweis dieser attraktiven Vermutung zum jetzigen Zeitpunkt (Anfang 2002) noch weit entfernt. Für Kreise, bipartite und vollständige Graphen läßt sich diese Vermutung recht leicht nachweisen.

Ist G speziell ein Graph der Ordnung n vom Maximalgrad Δ(G) = n − 1 mit der Eckenmenge E(G) = {x₁, x₂,…, x_n}, so kann man die Totalfärbungs-Vermutung durch den folgenden kleinen Trick auf ein Kantenfärbungsproblem zurückführen und dann mit Hilfe des Satzes von Vizing bestätigen. Man füge zu G eine Ecke w und die Kanten k₁ = wx₁, k₂ = wx₂, …, k_n = wx_n hinzu. Für den so entstandenen Graphen H gilt \begin{eqnarray}{\rm{\Delta}}(H)=n={\rm{\Delta}}(G)+1.\end{eqnarray}

Nach dem Satz von Vizing besitzt H eine (Δ(H)+1)-, also eine (Δ(G) + 2)-Kantenfärbung. Entfernt man nun aus H die Ecke w und färbt die Ecke x_i von G mit der Farbe der Kante k_i für alle i = 1, 2,…, n, so hat man aus der Kantenfärbung von H eine (Δ(G) + 2)-Totalfärbung von G gewonnen.

Mit Hilfe dieser Beweistechnik haben H.P. Yap, J.-F. Wang und Z.-F. Zhang 1989 sowie H.P. Yap und K.H. Chew 1992 die Totalfärbungs-Vermutung für Graphen G mit Δ(G) ≥ |E(G)|−5 nachgewiesen. A.V. Kostochka zeigte 1996 das gleiche für Graphen von kleinem Maximalgrad, genauer für Graphen G mit Δ(G) ≤ 5. Im Jahre 1989 bestätigte H.P. Yap die Totalfärbungs-Vermutung auch für die vollständigen k-partiten Graphen. Welche vollständigen k-partiten Graphen G die Gleichung \begin{eqnarray}{\chi}_{T}(G)={\rm{\Delta}}(G)+1,\end{eqnarray} und welche die Gleichung \begin{eqnarray}{\chi}_{T}(G)={\rm{\Delta}}(G)+2\end{eqnarray} erfüllen, ist jedoch bisher noch nicht ganz geklärt. Mit schwierigen Techniken aus der Eckenfärbungstheorie lieferten A.J.W. Hilton und H.R. Hind 1993 das folgende Ergebnis.

Ist G ein Graph der Ordnung n üom Maximalgrad\begin{eqnarray}{\rm{\Delta}}(G)\ge (3n)/4,\end{eqnarray}so gilt\begin{eqnarray}{\chi}_{T}(G)\le {\rm{\Delta}}(G)+2.\end{eqnarray}

Unter Ausnutzung probabilistischer Methoden gelangten 1998 M. Molloy und B. Reed mittels eines äußerst langen und komplizierten Beweises zu dem im Augenblick wohl tiefsten und besten Ergebnis im Zusammenhang mit der Totalfärbungs-Vermutung.

Es existiert eine absolute Konstante c, so daß für jeden Graphen G die Abschätzung\begin{eqnarray}{\chi}_{T}(G)\le {\rm{\Delta}}(G)+c\end{eqnarray}gilt.

Allerdings bemerkten die Autoren in ihrer Arbeit, daß es wohl nicht möglich sein wird, mit dem dort befolgten Weg die absolute Konstante c auf 2 zu drücken.

[1] Yap, H.P.: Total Colourings of Graphs. Lecture Notes in Mathematics 1623, Springer-Verlag Heidelberg/Berlin, 1996.