Polinomio cromático de un grafo simple desconectado

Question

Estoy trabajando en el siguiente ejercicio de colorear gráficos:

Demostrar que, si $G$ es un grafo simple desconectado, entonces su polinomio cromático $P_c(k)$ es el producto de los polinomios cromáticos de sus componentes. ¿Qué puedes decir sobre el grado del término no evanescente más bajo?

Estoy pensando en el hecho de que el polinomio cromático se calcula por separado para cada componente desconectado de $G$ entonces $P_c(k)$ sería el producto, pero no estoy nada seguro de este pensamiento. Tampoco estoy seguro de lo que significa "término más bajo no evanescente". Gracias de antemano por cualquier sugerencia o ayuda.

Answer 1

El polinomio cromático, $\chi(k)$ cuenta el número de maneras en que se puede colorear un gráfico con $k$ colores. Si el gráfico $G$ está desconectado, entonces la coloración de un componente no afecta a la coloración de otros componentes.

Si tiene dos componentes $G_1$ y $G_2$ y digamos por ejemplo que tienes 4 formas de colorear $G_1$ con 2 colores, y 2 formas de colores $G_2$ con 2 colores. Entonces, porque $G_1$ y $G_2$ no interactuar, tienes exactamente $4\times 2 = 8$ formas de colores $G$ con 2 colores.

Por cada $k$ el número de formas en que puede $k$ -color $G$ es el producto del número de formas de $k$ -color $G_1$ y del número de formas de $k$ -color $G_2$ .

Entonces, el menor término no evanescente es el menor término del polinomio : Sea el polinomio $\chi(k)=\sum_i a_i k^i$ . Se puede demostrar por inducción que (véase aquí ) el de su gráfico tiene $c$ componentes desconectados, entonces todo término $a_0,\ldots,a_{c-1}$ son nulas. Por lo tanto, el menor término no evanescente es $k^c$