Chromatisches Polynom

Anzahl der möglichen Knotenfärbungen in der Graphentheorie

Das chromatische Polynom gibt zu einem Graphen die Anzahl der möglichen Knotenfärbungen mit Farben an, d. h. die Anzahl der Färbungen aller Knoten des Graphen, so dass Knoten, die durch eine Kante verbunden sind, verschiedene Farben tragen.

Beispiele

Bearbeiten

Das chromatische Polynom eines Graphen mit   isolierten Knoten ist  . Jeder der   Knoten kann unabhängig von den anderen eine der   Farben annehmen.

Das chromatische Polynom eines vollständigen Graphen   ist

 

Die Farbe des ersten Knotens kann immer beliebig gewählt werden und für die Färbung des  -ten Knotens sind dann noch   Farben übrig.

Eigenschaften

Bearbeiten

Für jeden Graphen gibt es eine Zahl  , sodass   für alle  . Diese Zahl ist die chromatische Zahl des Graphen und gibt an, wie viele Farben für eine zulässige Knotenfärbung mindestens benötigt werden.

Es ist zunächst einmal nicht klar, dass   überhaupt ein Polynom in   ist, dies lässt sich jedoch induktiv zeigen, da für alle Kanten   gilt:   (wobei   derjenige Graph ist, der durch Kantenkontraktion von e entsteht).

Literatur

Bearbeiten
Bearbeiten