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\geq 0$ mit

   ${}P_{G}\left(k\right)\geq 1\,.$

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

   ${}k(k-1)\cdots (k-n+1)\leq P_{G}\left(k\right)\leq k^{n}\,.$

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

   ${}P_{G}\left(k\right)=\sum _{j=0}^{n}{\left(\sum _{\ell =j}^{n}(-1)^{\ell -j}{\binom {k}{\ell }}{\binom {\ell }{j}}\right)}P_{G}\left(j\right)\,.$

   Insbesondere ist das chromatische Polynom durch die Werte ${}P_{G}\left(0\right),P_{G}\left(1\right),\ldots ,P_{G}\left(n\right)$ festgelegt.

Zum Beweis, Alternativen Beweis erstellen