Listenfärbung

aus Wikipedia, der freien Enzyklopädie
Dies ist die aktuelle Version dieser Seite, zuletzt bearbeitet am 21. Juni 2022 um 17:50 Uhr durch imported>Entbert(1506124) (→‎Definition: Definition korrigiert. Einem v wird ja gerade nicht die ganze Menge F_v zugeordnet, sondern nur ein Element daraus. So auch näher am zitierten Diestel.).
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

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

Definition

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

Listcoloring.png

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

  • 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