Die Listenfärbung ist ein Begriff der Graphentheorie und eine Verallgemeinerung der Kantenfärbung und der Knotenfärbung.
Definition Bearbeiten
Ist ein Graph und eine Mengenfamilie beliebiger Mengen, so heißt eine gültige Knotenfärbung mit für alle Knoten des Graphen eine Färbung aus den Listen 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 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 bezeichnet. Formal ist , wobei der Kantengraph von ist.
Beispiel Bearbeiten
Für den oben Abgebildeten Graphen mit 5 Knoten ist zu jedem Knoten eine Liste von verfügbaren Farben für eine Knotenfärbung vorgegeben. Eine gültige Knotenfärbung aus den Listen wäre z. B.
Eigenschaften Bearbeiten
- Da Listenfärbungen eine Verallgemeinerung von gewöhnlichen Färbungen sind, gilt stets und . Dabei ist die Chromatische Zahl des Graphen ist und die Kantenchromatische Zahl.
- Sind alle Listen 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 wobei der Maximalgrad des Graphen ist.
- Vermutlich gilt für jeden Graphen (Listenfärbungsvermutung). Dies wurde aber bisher nicht bewiesen.
Literatur Bearbeiten
- Reinhard Diestel: Graphentheorie. 4. Auflage. Springer, Berlin 2010, ISBN 978-3-642-14911-5 (354 S., diestel-graph-theory.com).