棱柱图和反棱柱图的色多项式的可约性

ZCos666

棱柱图（Prism Graph）的色多项式为

\[P_n(k)=(k-1)\left[(1-k)^n+(3-k)^n\right]+(k^2-3k+3)^n+k^2-3k+1\]

不难发现，恒有因式$k(k-1)$，当$n\nmid2$时，还有因式$k-2$，于是令

\[f_n(k)=\begin{cases} \dfrac{1}{k(k-1)(k-2)}P_n(k)&n\nmid2\\[5pt] \dfrac{1}{k(k-1)}P_n(k)&n\mid2 \end{cases}\]

试证明或证伪：$n\ge2$时，$f_n(k)$在$\mathbb{Q}[k]$上不可约

反棱柱图（Antiprism Graph）的色多项式为

\[P_n(k)=(k-1)\left[\left(\frac{5-2 k-\sqrt{9-4 k}}{2}\right)^{n}+\left(\frac{5-2 k+\sqrt{9-4 k}}{2}\right)^{n}\right]+(k-2)^{2 n}+k^{2}-3 k+1\]

不难发现，恒有因式$k(k-1)(k-2)$，当$n\nmid3$时，还有因式$k-3$，于是令

\[f_n(k)=\begin{cases} \dfrac{1}{k(k-1)(k-2)(k-3)}P_n(k)&n\nmid3\\[5pt] \dfrac{1}{k(k-1)(k-2)}P_n(k)&n\mid3 \end{cases}\]

试证明或证伪：$f_n(k)$在$\mathbb{Q}[k]$上不可约

hbghlyj

相关：Galois groups of chromatic polynomials
cameroncounts.wordpress.com/2016/10/04/algebr … -of-chromatic-roots/

…graphs for which the chromatic polynomial is a product of a number of linear factors together with one “interesting” factor. Computation shows that this interesting factor is very often irreducible