I'm working in the following graph theroy/coloring excercise:
Prove that, if $G$ is a disconnected simple graph, then its chromatic polynomial $P_c(k)$ is the product of the chromatic polynomials of its components. What can you say about the degree of the lowest non-vanishing term?
I'm thinking about the fact that the chromatic polynomial is calculated separatedly for each disconnected component of $G$, then $P_c(k)$ would be the product, but I'm not sure at all about this thought. Also I'm not sure about what does "lowest non-vanishing term" means. Thanks in advance for any hint or help.
Best Answer
The chromatic polynomial,$\chi(k)$, counts the number of way you can color a graph with $k$ colors. If the graph $G$ is disconnected, then the coloring from one component does not affect the coloring from other components.
If you have two component $G_1$ and $G_2$, and let's say for example that you have 4 way to color $G_1$ with 2 colors, and 2 ways to colors $G_2$ with 2 colors. Then, because $G_1$ and $G_2$ do no interact, you have exactly $4\times 2 = 8$ ways to colors $G$ with 2 colors.
For every $k$, the number of ways you can $k$-color $G$ is the product of the number of ways to $k$-color $G_1$ and of the number of ways to $k$-color $G_2$.
Then, the least non-vanishing term is the lowest term in the polynomial : Let you polynomial be $\chi(k)=\sum_i a_i k^i$. You can show by induction that (see here) that of your graph has $c$ disconnected components, then all term $a_0,\ldots,a_{c-1}$ are null. Hence the least non-vanishing term is $k^c$