Stiergraph/Charakteristisches Polynom/Chromatisches Polynom/Aufgabe/Lösung

1. Wir nummerieren die Knotenpunkte von links nach rechts und von oben nach unten. Die Adjazenzmatrix ist

   ${\begin{pmatrix}0&0&1&0&0\\0&0&0&1&0\\1&0&0&1&1\\0&1&1&0&1\\0&0&1&1&0\end{pmatrix}}.$

   Das charakteristische Polynom ist die Determinante von

   ${\begin{pmatrix}X&0&-1&0&0\\0&X&0&-1&0\\-1&0&X&-1&-1\\0&-1&-1&X&-1\\0&0&-1&-1&X\end{pmatrix}}.$

   Wir entwickelen nach der ersten Spalte und erhalten

   ${}{\begin{aligned}\chi _{}&=X\cdot \det {\begin{pmatrix}X&0&-1&0\\0&X&-1&-1\\-1&-1&X&-1\\0&-1&-1&X\end{pmatrix}}-\det {\begin{pmatrix}0&-1&0&0\\X&0&-1&0\\-1&-1&X&-1\\0&-1&-1&X\end{pmatrix}}\\&=X^{2}\cdot \det {\begin{pmatrix}X&-1&-1\\-1&X&-1\\-1&-1&X\end{pmatrix}}-X\det {\begin{pmatrix}0&-1&0\\X&-1&-1\\-1&-1&X\end{pmatrix}}+X\det {\begin{pmatrix}-1&0&0\\-1&X&-1\\-1&-1&X\end{pmatrix}}+\det {\begin{pmatrix}-1&0&0\\0&-1&0\\-1&-1&X\end{pmatrix}}\\&=X^{2}\cdot \det {\begin{pmatrix}X&-1&-1\\-1&X&-1\\-1&-1&X\end{pmatrix}}+2X\det {\begin{pmatrix}-1&0&0\\-1&X&-1\\-1&-1&X\end{pmatrix}}+\det {\begin{pmatrix}-1&0&0\\0&-1&0\\-1&-1&X\end{pmatrix}}\\&=X^{2}{\left(X(X^{2}-1)+(-X-1)-(1+X)\right)}-2X(X^{2}-1)+X\\&=X{\left(X{\left(X(X^{2}-1)-2X-2\right)}-2(X^{2}-1)+1\right)}\\&=X{\left(X^{4}-5X^{2}-2X+3\right)}\end{aligned}}$

2. Eine zulässige Färbung ist insbesondere eine Färbung des Stierkopfes. Dieser ist ein vollständiger Graph mit drei Knotenpunkten und sein chromatisches Polynom ist ${}X(X-1)(X-2)$. Jede zulässige Färbung kann man auf den ganzen Stier zulässig ausdehnen, wobei für die Hörner jeweils nur die Farbe der anliegenden Schläfe ausgeschlossen ist. Deshalb ist das chromatische Polynom gleich

   ${}X(X-1)(X-2)(X-1)^{2}=X(X-1)^{3}(X-2)\,.$

Zur gelösten Aufgabe