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.

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.

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).

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

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

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