Definitionen

Eine Knotenfärbung bzw. einfach Färbung eines ungerichteten Graphen G=(V,E) ordnet jedem Knoten aus V eine natürliche Zahl zu, die auch Farbe genannt wird. Eine Färbung heißt zulässig oder gültig, falls je zwei benachbarten Knoten eine unterschiedliche Farbe zugewiesen wird.

Anders formuliert ist also eine zulässige Färbung eines Graphen eine Partition seiner Knotenmenge in unabhängige Mengen (eine Teilmenge der Knotenmenge V eines Graphen heißt unabhängig, falls sie keine zwei benachbarten Knoten enthält).

Eine Färbung, die k verschiedene Farben verwendet, heißt k-Färbung. Das kleinste k heißt chromatische Zahl und wird meist mit ?(G) bezeichnet.

Ein Graph, der 2-färbbar ist, heißt bipartit.

Der allgemeine Fall

Die Bestimmung der chromatischen Zahl eines Graphen ist NP-schwer (d.h. insbesondere, dass es vermutlich keinen aus Sicht der Komplexitätstheorie effizienten Algorithmus gibt, der dieses Problem löst).

Der zur Zeit praktisch beste Algorithmus beruht auf einem Spalten-Generierungs-Ansatz (siehe Literatur). Weiterhin gibt es viele Färbungsheuristiken, die nach bestimmten Methoden gute Färbungen suchen und somit im Erfolgsfall eine obere Schranke für die chromatische Zahl liefern.

Spezialfälle

Der Vier-Farbensatz besagt, dass die chromatische Zahl eines planaren Graphen höchstens 4 ist. Trotzdem ist auch für planare Graphen das Bestimmen der chromatischen Zahl NP-schwer.

Das Entscheidungsproblem, ob ein gegebener Graph bipartit ist, besitzt lineare Zeitkomplexität, und ist zum Beispiel mit Tiefensuche lösbar.

Für die folgenden Graphen ist die Bestimmung der chromatischen Zahl durch effiziente Algorithmen möglich:

• bipartite Graphen sind 2-färbbar.
• Wälder bzw. Bäume sind 2-färbbar, weil sie bipartit sind.
• Für perfekten Graphen existieren Polynomialzeitalgorithmen.

Weitere Sätze

Der Greedy-Algorithmus liefert als obere Schranke für die chromatische Zahl eines Graphen den Maximalgrad des Graphen plus 1. Beispiele, die zeigen, dass diese Abschätzung bestmöglich ist, sind Graphen mit Kreisen ungerader Länge und vollständige Graphen. Der Satz von Brooks zeigt aber, dass dies auch die einzigen Beispiele sind. Für jeden zusammenhängenden Graphen, der keine Kreise ungerader Länge enthält oder nicht vollständig ist, ist seine chromatische Zahl stets kleiner oder gleich dem Maximalgrad des Graphen.

Anwendungen

Stundenplanprobleme lassen sich als Graphfärbungsprobleme formulieren: Die Knoten des Graphen sind dabei die zu platzierenden Veranstaltungen, und eine Kante wird zwischen zwei Veranstaltungen eingefügt, die nicht gleichzeitig stattfinden können (in der Schule wären das z.B. Stunden, die von demselben Lehrer unterrichtet werden sowie Stunden in derselben Klasse). Die möglichen Farben entsprechen den zuteilbaren Zeitfenstern.

In gleicher Weise können beispielsweise Register-Zuweisungs-Probleme in Prozessoren, Bandbreiten-Zuweisung-Probleme und auch viele andere Probleme aus der Mathematik als Graphenfärbungsprobleme formuliert werden.

Kantenfärbungen

Ist G=(V,E) ein ungerichteter Graph ohne Mehrfachkanten und f eine Abbildung von E in die Menge der natürlichen Zahlen, so nennt man f eine Kantenfärbung von G. Man nennt f gültig, falls für je zwei beliebige benachbarte Kanten e₁ und e₂ gilt f(e₁)?f(e₂) und sagt G ist k-kantenfärbbar, falls es eine gültige Kantenfärbung von G gibt, so dass für alle e aus E gilt f(e)<k, also . Das kleinste k, für das G k-kantenfärbbar ist, nennt man den chromatischer Index oder die Kantenfärbungszahl des Graphen G.

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

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, ebenfalls NP-schwer.

Literatur

1. Anuj Mehrotra, Michael A. Trick: A column generation approach for graph coloring. INFORMS Journal on Computing Vol. 8, No. 4 (1996), Seiten 344-354. Online: http://mat.gsia.cmu.edu/trick/color.ps