polinomio cromático para el grafo del casco

Question

Estaba mirando el gráfico de Helm aquí

y miramos el polinomio cromático aquí ,

y he notado lo que creo que puede ser una discrepancia. Introduciendo 3 colores y 9 vértices de un polinomio cromático del grafo del timón (9 vértices es el número correcto de vértices para el grafo del timón con un subgrafo de 4 ciclos, ver enlace 1) da el resultado 0.

es decir, no es posible colorear un gráfico de casco con 3 colores.

Pero es claramente posible colorear un grafo de timón con un subgrafo de 4 ciclos, con 3 colores, aunque el grafo de timón con un subgrafo de 3 ciclos no puede ser coloreado con 3 colores.

Así que parece que el polinomio cromático está mal.

¿Es una discrepancia o estoy haciendo algo mal?

Answer 1

Mi opinión es que el OP (incorrectamente) utilizó $n=7$ o $n=9$ en el cálculo. De hecho, el valor correcto es $n=4$ :

$$z\left((1-z)^4(z-2)+(z-2)^4(z-1)^4\right)=\\=z^9-12 z^8+62 z^7-179 z^6+315 z^5-346 z^4+232 z^3-87 z^2+14 z$$

Obsérvese que el resultado es mónico de grado $9$ correspondiente a $9$ vértices. (o nota que $n=4$ correspondiente a $H_4$ )

Sustituyendo $z=3$ obtenemos $$3\left((1-3)^4(3-2)+(3-2)^4(3-1)^4\right)=3((-2)^4+2^4)=96$$