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

Gibt man für jede Ecke v eines Graphen G eine Liste L_v 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 (L_v)_v∈E(G) von Listen mit |L_v| = k für alle v ∈ E (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.

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.