Direkt zum Inhalt

Lexikon der Mathematik: Listenfärbung

Verallgemeinerung des Konzepts der Eckenfärbung und Kantenfärbung.

Gibt man für jede Ecke v eines Graphen G eine Liste Lv speziell an dieser Ecke erlaubter Farben vor, so kann man fragen, ob G eine Eckenfärbung mit Farben aus den jeweiligen Listen besitzt. Der Graph G heißt k-listenfärbbar, wenn für jede vorgegebene Familie (Lv)vE(G) von Listen mit |Lv| = k für alle vE (G) eine Eckenfärbung mit den Farben aus den entsprechenden Listen existiert. Die kleinste Zahl k ∈ ℕ, für die G noch k-listenfärbbar ist, wird listenchromatische Zahl χl (G) von G genannt.

Enthält z. B. jede Liste genau Δ(G) + 1 Farben, wobei Δ(G) der Maximalgrad des Graphen G ist, so erhält man ohne Mühe eine Listenfärbung von G, indem man sukzessive die Ecken so färbt, daß adjazente Ecken verschiedene Farben tragen. Insbesondere ergibt sich daraus die Abschätzung \begin{eqnarray}{\chi }_{l}(G)\le {\rm{\Delta }}(G)+1.\end{eqnarray}

Kantenfärbungen aus Listen sind analog definiert. Das kleinste k, für das G aus Listen von je k Farben stets kantenfärbbar ist, heißt listenchromatischer Index \({\chi }_{l}^{{\prime}}(G)\) von G. Man kann aber auch einfach \({\chi }_{l}^{{\prime}}(G)\) durch \begin{eqnarray}{\chi }_{l}^{{\prime}}(G)={\chi }_{l}(L(G))\end{eqnarray} über den Kantengraphen L(G) von G definieren. Der Spezialfall, daß in allen Listen die gleichen Farben enthalten sind, liefert sofort die folgenden Beziehungen zu der chromatischen Zahl χ(G) bzw. zu dem chromatischen Index χ′(G): \begin{eqnarray}{\chi }_{l}(G)\ge \chi (G)\,\,\,\,\mathrm{und}\,\,\,\,{\chi }_{l}^{{\prime}}(G)\ge {\chi }^{{\prime}}(G).\end{eqnarray}

In der ersten Ungleichung muß aber keineswegs immer das Gleichheitszeichen stehen. Dies erkennt man z. B. an dem skizzierten bipartiten Graphen B mit den angegebenen Listen aus 2 Farben. Beginnt man in der Mitte mit der Farbe 1 oder 2, so überzeugt man sich leicht davon, daß B nicht 2-listenfärbbar ist, aber es gilt natürlich χ(B) = 2.

Abbildung 1 zum Lexikonartikel Listenfärbung
© Springer-Verlag GmbH Deutschland 2017
 Bild vergrößern

Ein nicht 2-listenfarbbarer bipartiter Graph B mit χ(B) = 2

Um so erstaunlicher ist es, daß für Kantenfärbungen aus Listen kein entsprechendes Beispiel bekannt ist. Daraus resultiert die sogenannte Listen-färbungs-Vermutung von V.G. Vizing aus dem Jahre 1976:

Für jeden Graphen G gilt \({\chi }_{l}^{{\prime}}(G)=\chi ^{\prime} (G)\).

Durch einen überraschend kurzen Beweis konnte F. Galvin 1995 diese Listenfärbungs-Vermutung für bipartite Graphen bestätigen, die insbesondere eine Vermutung von J.Dinitz aus dem Jahre 1978 über lateinische Quadrate löst.

Ist G ein bipartiter Graph, so gilt \({\chi }_{l}^{{\prime}}(G)=\chi ^{\prime} (G)\).

Zusammen mit einem Satz von König folgt daraus noch \begin{eqnarray}{\chi }_{l}^{{\prime}}(G)={\chi }^{{\prime}}(G)={\rm{\Delta }}(G),\end{eqnarray} falls G bipartit ist.

Der große Durchbruch erfolgte dann 1996, als J.Kahn zeigte, daß die Listenfärbungs-Vermutung jedenfalls asymptotisch richtig ist.

Für jedes ϵ > 0 gilt \begin{eqnarray}{\chi }_{l}^{{\prime}}(G)\le (1+\varepsilon )\,{\rm{\Delta }}(G)\end{eqnarray}für alle Graphen Gmit hinreichend großem Δ(G).

Dennoch ist man von einem vollständigen Beweis der Listenfärbungs-Vermutung noch sehr weit entfernt.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos