I would like to find the chromatic polynomial of this graph:
I know the chromatic polynomial $k(k – 1)^{n-1}$ for a tree. Also
$$p_{G}(k)= p_{G-e}(k) – p_{G\cdot e}(k) $$
is a recurrence I have. I also know the chromatic polynomial for $C_{n}$, the cycle graph.
I am new to this type of problem. I tried to use this recurrence almost 10 times but still make mistakes because I think the formula I am getting is wrong.
I don't know if there is a quicker way than what I am trying but I always first try to remove edge $(1, 5)$ and then keep going to reduce it into a path.
Can someone please help me? I think I am overcomplicating this problem. I keep on getting recurrences very very long and I guess I keep making mistakes (the polynomial I'm getting isn't even degree $7$).
Best Answer
By thinking of $G$ as being obtained via a 2-clique-sum of $K_3$ and $C_5$ and then a 2-clique-sum of the result with $K_3$, you can compute \begin{align} p(G,x) &= \frac{p(K_3,x) p(C_5,x)}{x(x-1)}\cdot\frac{p(K_3,x)}{x(x-1)} \\ &= \frac{p(K_3,x)^2 p(C_5,x)}{x^2(x-1)^2} \\ &= \frac{(x(x-1)(x-2))^2((x-1)^5-(x-1))}{x^2(x-1)^2}\\ &=x(x-1)(x-2)^3(x^2-2x+2). \end{align}
A similar computation with $K_3$ in place of $C_5$ appears in the 1997 movie Good Will Hunting.