Listenfärbung

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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

Definition[Bearbeiten]

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: v \mapsto F_v für alle Ecken des Graphen eine Färbung aus den Listen  F_v oder Listenfärbung. Ein Graph heißt k-listenfärbbar, wenn er für alle Listen mit k Elementen stets eine Eckenfä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[Bearbeiten]

Listcoloring.png

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[Bearbeiten]

Literatur[Bearbeiten]