Non-uniqueness of Chromatic Polynomials

81 Views Asked by At

Consider the path graph of $3$ vertices. Let the vertices be labelled $1,2,3$. Let us start with $x$ colors. I can color the first vertex (vertex $1$) in $x$ ways, the next vertex (vertex $2$) in $x-1$ ways. This gives me the chromatic polynomial as $x(x-1)^2$.

But, now consider coloring the first vertex (vertex $1$) which can be done in $x$ ways. Then, I color the third vertex (vertex $3$), which can be done in $x$ ways (as $1$ and $3$ vertices are not adjacent). The last vertex (vertex $2$) can be colored in $(x-1)$ ways. This gives me the chromatic polynomial as $x^2(x-1)$. What is the reason for the non-uniqueness? Is my calculation wrong in the second case? Thanks beforehand.

1

There are 1 best solutions below

6
On BEST ANSWER

Your second counting is inaccurate. The number of choices for vertex 2 could be $x-1$ or $x-2$, depending on whether the colors for vertices 1 and 3 are equal. This variation means you cannot simply multiply $x^2$ by (number of ways to color vertex 2).

Instead this calls for splitting into two cases depending on the color choice for vertex 3:

If vertex 3 has a different color than vertex 1, there are $x-1$ choices for vertex 3 and $x-2$ choices for vertex 2: $x(x-1)(x-2)$ colorings.

If vertex 3 has the same color as vertex 1, there is only one choice for vertex 3 and $x-1$ for vertex 2: $x(1)(x-1)$ colorings.

The two cases sum to exactly $x(x-1)^2$ which matches the simpler argument.