I have the following graph:
And I need to find its chromatic polynomial.
Based in my notes, I have reached the following result:
$$Pg(x) = \frac{((x-1)^4 + (x-1))^2}{x(x-1)} $$.
It is because I have applied this formula:
$$Pg(x) = \frac{Pg1(x) Pg2(x)}{Pkr(x)} $$.
Taking the Bridge Graph and the previous formula, I have replaced with:
$$ Pg1(x) = Pg2(x) = Pc4(x)= (x-1)^4+(x-1) $$
Because both sub-graphs are cycles.
On the other hand, the Pkr(x) in this case is equals to Pk2(x). So, the chromatic polynomial for a complete graph with n = 2, could be expressed as :
$$x(x-1)$$
So, my main doubt is if this reasoning is right. Because I'm not sure about my resolution and I think that Ia have missing something in the final response.
Thanks a lot!
Best Answer
The formula $$ P_G(x) = \frac{P_{G_1}(x) \cdot P_{G_2}(x)}{P_{K_r}(x)} $$ that you are using is appropriate when $G$ is the clique sum of the graphs $G_1$ and $G_2$ along a copy of $K_r$.
The graph you give,
is not a clique sum of two cycles. Instead, it is a clique sum (along a $K_2$) of the graph induced by vertices $\{a,b,c,d,e\}$ and the graph induced by vertices $\{d,e,f,g,h\}$.
Both of these are not cycles, but cycles with an extra leaf vertex. Here is how we deal with that extra vertex. If the cycle has chromatic number $(x-1)^4+(x-1)$, then there are always $x-1$ ways to color the leaf vertex with a color different from its only neighbor, so in this case we have $P_{G_1}(x) = P_{G_2}(x) = (x-1)^5 + (x-1)^2$.
Applying the formula, we get $$ P_G(x) = \frac{[(x-1)^5 + (x-1)^2]^2}{x(x-1)} = x^8-9 x^7+36 x^6-82 x^5+114 x^4-96 x^3+45 x^2-9 x. $$ (A quick sanity check which this result passes and yours does not is that the degree of $P_G(x)$ must be the number of vertices in $G$.)