Kantenfärbung

Zuordnung einer Farbe zu jeder Kante eines Graphen

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

Bearbeiten
 
Ein Multigraph mit einer 9-Kantenfärbung.
 
Eine Kantenfärbung des   mit 7 Farben.

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

Bearbeiten

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

Bearbeiten

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 einem 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.[1]

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.[2]

Zusammenhang mit Matchings

Bearbeiten
 
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  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.[1]

Dualität zur Eckenfärbung

Bearbeiten

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

Bearbeiten

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

Bearbeiten
Bearbeiten

Einzelnachweise

Bearbeiten
  1. a b Alexander Soifer: The Mathematical Coloring Book. In: Springer-Verlag. 2008.
  2. Norman Biggs: An edge-colouring problem. In: American Mathematical Monthly. 79. Jahrgang, Nr. 9, 1972, S. 1018–1020, doi:10.2307/2318076.