Chromatisches Polynom

Das chromatische Polynom ${\displaystyle \chi (G,\lambda )}$ gibt zu einem Graphen ${\displaystyle G}$ die Anzahl der möglichen Knotenfärbungen mit ${\displaystyle \lambda }$ 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

Das chromatische Polynom eines Graphen mit ${\displaystyle n}$ isolierten Knoten ist ${\displaystyle \chi (G,\lambda )=\lambda ^{n}}$. Jeder der ${\displaystyle n}$ Knoten kann unabhängig von den anderen eine der ${\displaystyle \lambda }$ Farben annehmen.

Das chromatische Polynom eines vollständigen Graphen ${\displaystyle K_{n}}$ ist

${\displaystyle \chi (K_{n},\lambda )=\prod _{i=0}^{n-1}(\lambda -i)=\lambda (\lambda -1)\cdots (\lambda -n+1)}$

Die Farbe des ersten Knotens kann immer beliebig gewählt werden und für die Färbung des ${\displaystyle (i+1)}$-ten Knotens sind dann noch ${\displaystyle \lambda -i}$ Farben übrig.

Eigenschaften

Für jeden Graphen gibt es eine Zahl ${\displaystyle \chi (G)}$, sodass ${\displaystyle \chi (G,\lambda )=0}$ für alle ${\displaystyle \lambda <\chi (G)}$. 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 ${\displaystyle \chi }$ überhaupt ein Polynom in ${\displaystyle \lambda }$ ist, dies lässt sich jedoch induktiv zeigen, da für alle Kanten ${\displaystyle e\in E}$ gilt: ${\displaystyle \chi (G,\lambda )=\chi (G\setminus \{e\},\lambda )-\chi (G/e,\lambda )}$ (wobei ${\displaystyle G/e}$ derjenige Graph ist, der durch Kantenkontraktion von e entsteht).

Literatur

• Herbert Wilf, "Algorithms and Complexity", Prentice-Hall, 1986
• William Thomas Tutte: Graph Theory. Addison-Wesley, 1984, ISBN 0-201-13520-5
• Swamy M., Thulasiraman K.: Graphs, Networks and Algorithms. Krieger Pub. Co., 1980, ISBN 0-471-03503-3
• Martin Aigner: Combinatorial theory. Springer, 1979, ISBN 0-387-90376-3
• Graham R. (Ed.), Grötschel M. (Ed.), László L. (Ed.): Handbook of Combinatorics. Vol. 1, Elsevier, 1995, ISBN 0-262-07170-3

Weblinks

Wikiversity: Eine Vorlesung über das chromatische Polynom im Rahmen eines Kurses zur diskreten Mathematik – Kursmaterialien

• Eric W. Weisstein: Chromatic Polynomial. In: MathWorld (englisch).