Listenfärbung

Die Listenfärbung ist ein Begriff der Graphentheorie und eine Verallgemeinerung der Kantenfärbung und der Knotenfärbung.

Definition

Ist $G=(V,E)$ ein Graph und $(F_{v})_{v\in V}$ eine Mengenfamilie beliebiger Mengen, so heißt eine gültige Knotenfärbung $c$ mit $c(v)\in F_{v}$ für alle Knoten $v\in V$ des Graphen eine Färbung aus den Listen $F_{v}$ oder Listenfärbung. Ein Graph heißt k-listenfärbbar, wenn für alle Listen mit k Elementen stets eine Knotenfärbung aus diesen Listen existiert. Das kleinste k, so dass der Graph k-listenfärbbar ist, heißt listenchromatische Zahl des Graphen und wird mit $ch(G)$ bezeichnet.

Anschaulich wird also zu jedem Knoten eine Liste mit verfügbaren Farben vorgegeben und der Graph muss daraufhin so gefärbt werden, dass zwei benachbarte Knoten nie dieselbe Farbe haben.

Analog lassen sich Kantenfärbungen aus Listen definieren. Das kleinste k, so dass G für alle Listen mit je k Farben kantenfärbbar ist, wird listenchromatischer Index genannt und mit $ch'(G)$ bezeichnet. Formal ist $ch'(G)=ch(L(G))$, wobei $L(G)$ der Kantengraph von $G$ ist.

Beispiel

Für den oben Abgebildeten Graphen mit 5 Knoten ist zu jedem Knoten $i$ eine Liste $F_{i}$ von verfügbaren Farben für eine Knotenfärbung vorgegeben. Eine gültige Knotenfärbung aus den Listen wäre z. B. $c(3)=c(5)=b\;,\;c(1)=c(4)=a\;,c(2)=e$

Eigenschaften

• Da Listenfärbungen eine Verallgemeinerung von gewöhnlichen Färbungen sind, gilt stets $ch(G)\geq \chi (G)$ und $ch'(G)\geq \chi '(G)$. Dabei ist $\chi (G)$ die Chromatische Zahl des Graphen ist und $\chi '(G)$ die Kantenchromatische Zahl.
• Sind alle Listen $F_{v}$ gleich, so entspricht die Listenfärbung genau der Kantenfärbung bzw. Knotenfärbung.
• Jeder planare Graph ist 5-Listenfärbbar.
• Für jeden bipartiten Graph gilt $ch'(G)=\chi '(G)=\Delta (G)$ wobei $\Delta (G)$ der Maximalgrad des Graphen ist.
• Vermutlich gilt für jeden Graphen $ch'(G)=\chi '(G)$ (Listenfärbungsvermutung). Dies wurde aber bisher nicht bewiesen.