Chromatisches Polynom/Erste Eigenschaften/Fakt

Für das chromatische Polynom gelten die folgenden Aussagen.

1. Die chromatische Zahl von $G$ ist die minimale Zahl  $k\ge 0$  mit

   $P_G\left(k\right)\ge 1.$

2. Mit  $n=\mathrm{\#}\left(V\right)$  gelten die Abschätzungen

   $k(k-1)\cdots (k-n+1)\le P_G\left(k\right)\le k^n.$

3. Für  $k\ge \mathrm{\#}\left(V\right)+1=n+1$  ist

   $P_G\left(k\right)=\sum _{j=0}^n(\sum _{\ell =j}^n(-1{)}^{\ell -j}(\genfrac{}{}{0ex}{}{k}{\ell })(\genfrac{}{}{0ex}{}{\ell }{j}))P_G\left(j\right).$

   Insbesondere ist das chromatische Polynom durch die Werte $P_G\left(0\right),P_G\left(1\right),\dots ,P_G\left(n\right)$ festgelegt.

Zum Beweis, Alternativen Beweis erstellen