Kantenfärbung

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

In der Graphentheorie ist eine Kantenfärbung eine Abbildung, welche jeder Kante eines Graphen eine (abstrakte) Farbe zuordnet. Der Begriff ist eng verwandt zur Knotenfärbung.

Definition[Bearbeiten]

Ein Multigraph mit einer neunfarbigen Kantenfärbung.
Eine Kantenfärbung des  K_8 mit 7 Farben.

Für einen ungerichteten Multigraph 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)\ne f(e_2). Besitzt G eine 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 G 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[Bearbeiten]

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(G) nennt man Klasse 1-Graphen, Graphen mit \chi'(G)=\Delta(G)+1 nennt man Klasse 2-Graphen (da die Abschätzung des Satzes nicht für Multigraphen gelten, werden Multigraphen Klasse 2-Graphen genannt, wenn \chi'(G)>\Delta(G) 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'(G)=\Delta(G). Damit sind alle bipartiten Graphen Klasse 1-Graphen.

Dualität zur Eckenfärbung[Bearbeiten]

Die Bestimmung einer Kantenfärbung ist zur Bestimmung einer Eckenfärbung in der Weise dual, dass eine Kantenfärbung eines Graphen  G genau eine Knotenfärbung des Kantengraphen L(G) ist. Daraus folgt, dass \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[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.

Weblinks[Bearbeiten]

Literatur[Bearbeiten]