Chromatisches Polynom/Konstruktionen/Fakt

Für das chromatische Polynom

gelten die folgenden Eigenschaften.

1. Es sei ${}e\in E$ eine Kante von ${}G$ mit dem zugehörigen Kontraktionsgraphen ${}G/e$. Dann gilt

   ${}P_{G}=P_{G\setminus \{e\}}-P_{G/e}\,.$

2. Bei einer disjunkten Vereinigung von zwei Graphen ${}G=G_{1}\uplus G_{2}$ ist

   ${}P_{G}=P_{G_{1}}\cdot P_{G_{2}}\,.$

Zum Beweis, Alternativen Beweis erstellen