Kantenfärbung

Eine Kantenfärbung ist eine Abbildung in der Graphentheorie, die jeder Kante eines Graphen eine (abstrakte) Farbe zuordnet. Eine Kantenfärbung heißt gültig oder zulässig, wenn für jeden Knoten des Graphen gilt: Alle am Knoten anliegenden Kanten haben unterschiedliche Farben.

Der Begriff ist eng verwandt mit der Knotenfärbung.

Definition

Ein Multigraph mit einer 9-Kantenfärbung.

Eine Kantenfärbung des $K_{8}$ mit 7 Farben.

Für einen ungerichteten Multigraphen $G=(V,E)$ nennt man eine Abbildung $f\colon E\rightarrow C\subseteq \mathbb {N} _{0}$ der Kantenmenge in die Menge der natürlichen Zahlen eine Kantenfärbung von $G$. Die Elemente aus $C$ werden in diesem Zusammenhang Farben genannt. Man nennt $f$ gültig oder zulässig, falls für je zwei beliebige benachbarte Kanten $e_{1}$ und $e_{2}$ gilt, dass $f(e_{1})\neq f(e_{2})$. Besitzt $G$ eine gültige Kantenfärbung $f$, so dass höchstens $k$ Farben im Bildbereich von $f$ auftreten, nennt man $G$ $k$-kantenfärbbar.

Das kleinste $k$, für das ein Graph $k$-kantenfärbbar ist, heißt chromatischer Index, Kantenfärbungszahl oder auch kantenchromatische Zahl des Graphen $G$ und wird meist mit $\chi '(G)$ bezeichnet.

Eigenschaften

Nach dem Satz von Vizing ist der chromatische Index eines einfachen Graphen $G$ mindestens so groß wie sein Maximalgrad, aber höchstens eins größer als dieser, also formal:

$\Delta (G)\;\leq \;\chi ^{\prime }(G)\;\leq \;\Delta (G)+1$

Graphen mit $\chi '(G)=\Delta \left(G\right)$ nennt man Klasse-1-Graphen, Graphen mit $\chi '\left(G\right)=\Delta \left(G\right)+1$ nennt man Klasse-2-Graphen, da die Abschätzung des Satzes nicht für Multigraphen gilt, werden Multigraphen Klasse-2-Graphen genannt, wenn $\chi '\left(G\right)>\Delta \left(G\right)$ gilt. Zu entscheiden, ob ein Graph Klasse 1 oder Klasse 2 ist (Klassifizierungsproblem), ist NP-vollständig. Das heißt, obwohl der Maximalgrad leicht zu bestimmen ist und der chromatische Index nur einen von zwei möglichen Werten annehmen kann, ist das Problem, für einen gegebenen Graphen genau diesen einen Wert zu bestimmen, NP-schwer.

Für bipartite Graphen ist $\chi '\left(G\right)=\Delta \left(G\right)$. Damit sind alle bipartiten Graphen Klasse-1-Graphen.

Beispiel

Bei einem zyklischen Graphen können die Kanten mit zwei Farben gefärbt sein, wenn die Länge des Zyklus gerade ist. Wenn die Länge jedoch ungerade ist, werden drei Farben benötigt.

Ein vollständiger Graph $K_{n}$ mit $n$ Knoten ist mit $n-1$ Farben kantenfärbbar, wenn $n$ eine gerade Zahl ist. Dies ist ein Sonderfall des Satz von Baranyai. Wenn $V(K_{n})=\{0,\ldots ,n-1\}$, so ist nämlich durch $f(\{k,n-1\})=k$ und $f(\{i,j\})=k\iff i+j\equiv 2k\mod n-1$ ($i,j\in \{0,\ldots ,n-2\}\setminus \{k\}$) eine zulässige Färbung mit den Farben $0,\ldots ,n-2$ gegeben. Soifer liefert hierfür die folgende geometrische Konstruktion: Es werden $n$ Knoten an den Ecken und in der Mitte eines regelmäßigen Polygons mit $n-1$ Ecken betrachtet. Färben Sie für jede Farbklasse jeweils eine Kante von der Mitte zu einen der übrigen Knoten und alle zu dieser Kante senkrecht stehenden Kanten ein. Wenn $n$ jedoch ungerade ist, werden $n$ Farben benötigt: Jede Farbe kann nur für ${\tfrac {n-1}{2}}$ Kanten verwendet werden, ein ${\tfrac {1}{n}}$ der Gesamtmenge.

Mehrere Autoren haben Kantenfärbungen der ungeraden Graphen untersucht, $n$-reguläre Graphen, in denen die Knoten Teams von $n-1$ Spielern darstellen, die aus einem Menge von $2\cdot n-1$ Spielern ausgewählt wurden, und in denen die Kanten mögliche Begegnungen dieser Teams darstellen, mit einem Spieler als "ungerader Mann", der das Spiel leitet. Der Fall $n=3$ ergibt den bekannten Petersen-Graphen. Biggs erklärt das Problem für $n=6$. Die Spieler möchten einen Zeitplan für diese Begegnungen finden, so dass jedes Team jedes seiner 6 Spiele an verschiedenen Wochentagen spielt, wobei alle Teams sonntags frei haben. Das heißt, sie formalisieren das Problem mathematisch und möchten eine 6-Kantenfärbung des 6-regulären ungeraden Graphen $O_{n}$ finden. Wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} gleich 3, 4 oder 8 ist, erfordert eine Kantenfärbung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle O_n} genau Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n + 1} Farben, aber wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} gleich 5, 6 oder 7 ist, werden nur Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Farben benötigt.

Zusammenhang mit Matchings

Dieser 3-reguläre planare Graph hat 16 Knoten und 24 Kanten, aber ein maximales Matching mit nur 7 Kanten. Daher sind 4 Farben für jede Kantenfärbung erforderlich.

Ein Matching in einem Graphen ist eine Menge von Kanten, von denen keine zwei benachbart sind. Ein perfektes Matching ist ein Matching, das Kanten enthält, die alle Knoten des Graphen berühren, und ein maximales Matching ist ein Matching, das so viele Kanten wie möglich enthält. Bei einer Kantenfärbung darf die Menge von Kanten mit einer Farbe nicht benachbart sein, damit sie ein Matching bilden. Das heißt, eine gültige Kantenfärbung ist dasselbe wie eine Aufteilung des Graphen in disjunkte Matchings.

Wenn die Größe eines maximalen Matching in einem bestimmten Graphen klein ist, sind viele Matchings erforderlich, um alle Kanten des Graphen abzudecken. Anders ausgedrückt bedeutet das, dass jede Kantenfärbung des Graphen mindestens Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tfrac{m}{b}} verschiedene Farben verwenden muss, wenn ein Graph insgesamt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} Kanten hat und höchstens Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b} Kanten zu einer maximalen Übereinstimmung gehören können. Beispielsweise hat der in der Abbildung gezeigte 3-reguläre planare Graph 16 Knoten und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m = 24} Kanten. In diesem Graphen kann es kein perfektes Matching geben. Wenn der mittlere Knoten in einem Matching enthalten ist, können die verbleibenden Knoten in drei verschiedenen Zusammenhangskomponenten mit vier, fünf und fünf Knoten gruppiert werden, und die Komponenten mit einer ungeraden Anzahl von Knoten können keine perfekten Matchings enthalten. Der Graph hat jedoch maximale Matchings mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b = 7} Kanten. Daher ist die Anzahl der Farben, die für eine Kantenfärbung des Graphen benötigt werden, mindestens Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tfrac{m}{b} = \tfrac{24}{7}} , und weil die Anzahl der Farben eine ganze Zahl sein muss, sind es mindestens 4 Farben.

Für einen regulären Graphen mit Knotengrad Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} , der kein perfektes Matching hat, kann diese Untergrenze verwendet werden, um zu zeigen, dass mindestens Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k + 1} Farben benötigt werden. Dies gilt insbesondere für einen regulären Graphen mit einer ungeraden Anzahl von Knoten, zum Beispiel die ungeraden vollständigen Graphen. Für solche Graphen muss Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} nach dem Handschlaglemma selbst gerade sein. Die Ungleichung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \chi'\left(G\right) \geq \tfrac{m}{b}} erklärt jedoch nicht vollständig den chromatischen Index jedes regulären Graphen, weil es reguläre Graphen gibt, die perfekte Matchings haben, aber nicht k-kantenfärbbar sind. Zum Beispiel ist der Petersen-Graph regulär mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m = 15} Kanten und hat ein perfektes Matching mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b = 5} Kanten, aber er hat keine Kantenfärbung mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tfrac{m}{b} = \tfrac{15}{5} = 3} Farben.

Dualität zur Eckenfärbung

Die Bestimmung einer Kantenfärbung ist zur Bestimmung einer Knotenfärbung in der Weise dual, dass eine Kantenfärbung eines Graphen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G } genau eine Knotenfärbung des Kantengraphen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L(G)} ist. Daraus folgt, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \chi'(G) = \chi(L(G))} gilt. Die kantenchromatische Zahl eines Graphen ist also genau die chromatische Zahl des Kantengraphen. Trotz dieses engen Zusammenhangs sind die Probleme unterschiedlich schwer zu lösen und die verfügbaren Abschätzungen unterscheiden sich deutlich.

Verallgemeinerungen

Eine wesentliche Verallgemeinerung der Kantenfärbung ist der Begriff der Listenfärbung. Hier wird für jede Kante (oder jeden Knoten) eine Liste mit verfügbaren Farben vorgegeben und der Graph soll nun eine gültige Kantenfärbung aus diesen Listen erhalten. Des Weiteren gibt es die Totalfärbung, bei der sowohl Knoten als auch Kanten gefärbt werden sollen.

Literatur

• Reinhard Diestel: Graphentheorie. 4. Auflage. Springer, Berlin 2010, ISBN 978-3-642-14911-5 (354 Seiten, Online-Version). 

Weblinks

• Wolfram Mathworld: "Edge Chromatic Number"
• Wolfram Mathworld: "Edge Coloring"