I have the following graph:

Bridge Graph with N = 8

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 :


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!


2 Answers 2


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, enter image description here

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$.)


Using standard techniques:

$$x^8-9 x^7+36 x^6-82 x^5+114 x^4-96 x^3+45 x^2-9 x$$


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .