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 

Für einen ungerichteten Multigraphen  nennt man eine Abbildung  der Kantenmenge in die Menge der natürlichen Zahlen eine Kantenfärbung von . Die Elemente aus  werden in diesem Zusammenhang Farben genannt. Man nennt  gültig oder zulässig, falls für je zwei beliebige benachbarte Kanten  und  gilt, dass . Besitzt  eine gültige Kantenfärbung , so dass höchstens  Farben im Bildbereich von  auftreten, nennt man  -kantenfärbbar.

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

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

Graphen mit  nennt man Klasse-1-Graphen, Graphen mit  nennt man Klasse-2-Graphen, da die Abschätzung des Satzes nicht für Multigraphen gilt, werden Multigraphen Klasse-2-Graphen genannt, wenn  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 . 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  mit  Knoten ist mit  Farben kantenfärbbar, wenn  eine gerade Zahl ist. Dies ist ein Sonderfall des Satz von Baranyai. Wenn , so ist nämlich durch  und  () eine zulässige Färbung mit den Farben  gegeben. Soifer liefert hierfür die folgende geometrische Konstruktion: Es werden  Knoten an den Ecken und in der Mitte eines regelmäßigen Polygons mit  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  jedoch ungerade ist, werden  Farben benötigt: Jede Farbe kann nur für  Kanten verwendet werden, ein  der Gesamtmenge.

Mehrere Autoren haben Kantenfärbungen der ungeraden Graphen untersucht, -reguläre Graphen, in denen die Knoten Teams von  Spielern darstellen, die aus einem Menge von  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  ergibt den bekannten Petersen-Graphen. Biggs erklärt das Problem für . 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  finden. Wenn  gleich 3, 4 oder 8 ist, erfordert eine Kantenfärbung von  genau  Farben, aber wenn  gleich 5, 6 oder 7 ist, werden nur  Farben benötigt.

Zusammenhang mit Matchings 

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 verschiedene Farben verwenden muss, wenn ein Graph insgesamt  Kanten hat und höchstens  Kanten zu einer maximalen Übereinstimmung gehören können. Beispielsweise hat der in der Abbildung gezeigte 3-reguläre planare Graph 16 Knoten und  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  Kanten. Daher ist die Anzahl der Farben, die für eine Kantenfärbung des Graphen benötigt werden, mindestens , und weil die Anzahl der Farben eine ganze Zahl sein muss, sind es mindestens 4 Farben.

Für einen regulären Graphen mit Knotengrad , der kein perfektes Matching hat, kann diese Untergrenze verwendet werden, um zu zeigen, dass mindestens  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  nach dem Handschlaglemma selbst gerade sein. Die Ungleichung  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  Kanten und hat ein perfektes Matching mit  Kanten, aber er hat keine Kantenfärbung mit  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  genau eine Knotenfärbung des Kantengraphen  ist. Daraus folgt, dass  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

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

Einzelnachweise 

Grundbegriff (Graphentheorie)