Es sei G ein Graph und K(G) die Kantenmenge von G. Dann nennt man eine Abbildung h : K(G) → {1, 2, …, k} mit der Eigenschaft, daß h(l₁) ≠ h(l₂) für alle inzidenten Kanten l₁ und l₂ aus K(G) gilt, Kantenfärbung oder genauer k-Kantenfärbung von G, und der Graph G heißt k-kantenfärbbar. Besitzt der Graph G eine k-Kantenfärbung, aber keine (k − 1)-Kantenfärbung, so heißt k chromatischer Index von G, in Zeichen \(k=\chi ^{\prime} (G)\).

Färbt man jede Kante eines Graphen mit einer anderen Farbe, so führt das zu einer Kantenfärbung, womit die Existenz des chromatischen Index gesichert ist. Bezeichnet man mit Δ(G) den Maximalgrad eines Graphen G, so erhält man unmittelbar \begin{eqnarray}\Delta (G)\le \chi ^{\prime} (G)\le |K(G)|,\end{eqnarray} und D.König hat 1916 gezeigt, daß alle bipartiten GraphenB die untere Schranke annehmen, d. h., es gilt immer (sogar für bipartite Multigraphen) \(\chi ^{\prime} (B)=\Delta (B)\). Im Jahre 1949 hat C.E.Shannon die bessere obere Schranke \(\chi ^{\prime} (G)\le 3\Delta (G)/2\) für beliebige Graphen G gegeben.

Der Begriff der Kantenfärbung ist einer der ältesten in der Graphentheorie. Er wurde schon 1880 von P.G. Tait eingeführt, der nachgewiesen hat, daß die Länder einer normalen und 3-regulären LandkarteL genau dann mit 4 Farben gefärbt werden können, wenn L eine 3-Kantenfärbung besitzt.

Ist h eine k-Kantenfärbung von G und K_i die Menge aller Kanten von G mit der Farbe i, so nennen wir K_i Farbenklasse. Damit ist jede Farbenklasse ein Matching von G, und es gilt \begin{eqnarray}\displaystyle \underset{i=1}{\overset{k}{\cup }}{K}_{i}=K(G)\end{eqnarray} mit K_i ∩ K_j = Ø für alle 1 ≤ i< j ≤ k. Daher liefert jede k-Kantenfärbung eine Zerlegung der Kantenmenge in k kantendisjunkte Matchings. Umgekehrt kann natürlich durch jede solche Zerlegung eine Kantenfärbung definiert werden.

Trotz der angegebenen Beziehungen zur Landkartenfärbung und Matchingtheorie hat sich die Kantenfärbung zu einer eigenständigen Disziplin innerhalb der Graphentheorie entwickelt. Dies ist auf die zentralen Resultate von V.G.Vizing aus den sechziger Jahren des 20. Jahrhunderts zurückzuführen. Sein berühmtestes Ergebnis, Satz von Vizing (1964) genannt, liefert eine erstaunlich scharfe obere Schranke für den chromatischen Index.

Ist G ein Graph, so gilt\begin{eqnarray}\Delta (G)\le \chi ^{\prime} (G)\le \Delta (G)+1.\end{eqnarray}

Damit teilt der Satz von Vizing die Graphen hinsichtlich ihres chromatischen Index in zwei Klassen ein. Ein Graph G heißt Klasse 1-Graph oder Klasse 1, falls \(\chi ^{\prime} (G)=\Delta (G)\) ist, anderenfalls heißt G Klasse 2-Graph oder Klasse 2. Die Frage, welche Graphen Klasse 1 und welche Klasse 2 sind, nennt man heute Klassifizierungsproblem. Die Bedeutung und Schwierigkeit dieses Problems wird offensichtlich, wenn man sich vergegenwärtigt, daß seine Lösung nach dem oben genannten Ergebnis von Tait den Vier-Farben-Satz implizieren würde. Darüber hinaus wurde 1981 von I. Holyer die NP-Vollständigkeit des Klassifizierungsproblems nachgewiesen, sogar für kubische Graphen.

Obwohl dieses Problem im wesentlichen ungelöst ist, kann man sagen, daß Klasse 2-Graphen relativ selten auftreten. Denn in dem folgenden Sinne haben P. Erdös und R.J. Wilson 1977 gezeigt, daß fast alle Graphen Klasse 1 sind.

Ist P(n) die Wahrscheinlichkeit dafür, daß ein Zufallsgraph der Ordnung n Klasse 1 ist, so gilt\begin{eqnarray}\mathop{\mathrm{lim}}\limits_{n\to \infty }P(n)=1.\end{eqnarray}

Reguläre Graphen sind genau dann Klasse 1, wenn sie eine 1-Faktorisierung besitzen. Beispiele von Klasse 1-Graphen sind die bipartiten Graphen und die vollständigen Graphen gerader Ordnung. Dagegen sind reguläre Graphen ungerader Ordnung, reguläre Graphen gerader Ordnung mit einer Artikulation und der sog. Petersen-Graph Klasse 2.

Um mehr über Klasse 2-Graphen zu erfahren, hat man die sogenannten kantenkritischen Graphen eingeführt. Ein zusammenhängender Klasse 2-Graph G heißt kantenkritisch, falls für jede Kante k ∈ K(G) die Ungleichung \begin{eqnarray}\chi ^{\prime} (G-k)\lt \chi ^{\prime} (G)\end{eqnarray} gilt. Es ist recht leicht zu sehen, daß ein kantenkritischer Graph keine Artikulation besitzt. Bezeichnen wir für eine Ecke v eines Graphen G mit \({d}_{G}^{\ast }(v)\) die Anzahl der mit v adjazenten Ecken maximalen Grades, so hat das zentrale Ergebnis über kantenkritische Graphen, das Vizing 1965 entdeckt hat, und weltweit den Namen Vizings Adjazenz Lemma trägt, die folgende Form:

Sind v und w zwei adjazente Ecken in einem kantenkritischen Graphen G, und ist d_G(w) der Grad der Ecke w, so gilt\begin{eqnarray}{d}_{G}^{\ast }(v)\ge {\rm{max}}\{2,\Delta (G)-{d}_{G}(w)+1\}.\end{eqnarray}

Damit besitzt jeder kantenkritische Graph mindestens drei Ecken maximalen Grades. Darüber hinaus hat Vizing in der gleichen Arbeit gezeigt, daß ein Klasse 2-Graph G für jedes p = 2, 3, …, Δ(G) einen kantenkritischen Teilgraphen H_p mit Δ(H_p) = p besitzt. Aus den letzten beiden Ergebnissen folgt unmittelbar, daß jeder Graph mit höchstens zwei Ecken maximalen Grades Klasse 1 ist.

Als weitere Anwendung der kantenkritischen Graphen hat Vizing 1965 noch bewiesen, daß alle planaren GraphenG vom Maximalgrad Δ(G) ≥ 8 Klasse 1 sind. In dieser Arbeit äußerte er die nach wie vor ungelöste Vermutung, daß sogar die planaren Graphen G mit Δ(G) ≥ 6 Klasse 1 sind. Im Fall 3 ≤ Δ ≤ 5 gibt es sowohl planare Klasse 1-Graphen als auch planare Klasse 2-Graphen G mit Δ(G) = Δ.

Unter Ausnutzung des Vizingschen Adjazenz Lemmas ist es A.G. Chetwynd und A.J.W. Hilton 1985 gelungen, alle Graphen mit genau drei Ecken maximalen Grades zu klassifizieren.

Ein zusammenhängender Graph G mit genau drei Ecken maximalen Grades ist dann und nur dann Klasse 2, wenn G von ungerader Ordnung n = 2p + 1 ist, und die Kantenmenge des Komplementärgraphen \(\overline{G}\)aus einem (p – 1)-elementigen Matching besteht.

Mit viel höherem Aufwand haben Chetwynd und Hilton auch die Graphen mit genau vier Ecken maximalen Grades klassifiziert.

Möchte man das Klassifizierungsproblem bei beliebig vorgegebener Anzahl der Ecken maximalen Grades lösen, so benötigt man zusätzlich eine Minimalgradbedingung, damit die zur Verfügung stehenden Hilfsmittel und Methoden Früchte tragen. Die diesbezüglich besten Ergebnisse gehen auf T. Niessen und L.Volkmann (1990) und K.H. Chew (1996) zurück, von denen wir hier nur das am einfachsten zu formulierende von Niessen und Volkmann vorstellen wollen.

Es sei G ein Graph der Ordnung 2p mit genau ζ Ecken maximalen Grades.

Erfüllt der Minimalgrad δ(G) die Bedingung \begin{eqnarray}\delta (G)\ge p+\zeta-2,\end{eqnarray}so ist G Klasse 1.

Literatur

[1] Chartrand, G.; Lesniak, L.: Graphs and Digraphs. Chapman and Hall London, 1996.

[2] Volkmann, L.: Fundamente der Graphentheorie. Springer Wien New York, 1996.