Chromatisches Polynom
# Chromatisches Polynom

Das chromatische Polynom $\chi (G,\lambda )$ gibt zu einem Graphen $G$ die Anzahl der möglichen Knotenfärbungen mit $\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 $n$ isolierten Knoten ist $\chi (G,\lambda )=\lambda ^{n}$. Jeder der $n$ Knoten kann unabhängig von den anderen eine der $\lambda$ Farben annehmen.

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

    $\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 $(i+1)$-ten Knotens sind dann noch $\lambda -i$ Farben übrig.

## Eigenschaften

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

