Help me calculating chromatic polynomial of this subgraph

493 Views Asked by At

subgraph

This is the subgraph. I just wanted to do a couple of exercises with chromatic polynomials, but around the web are pretty standard ones, so i came up with this one myself. I thought it's pretty straightforward.

It is: i color $A$ with $x$ colors, automatically $B$ and $C$ are both different, so $B$ is colored with $x-1$ colors and $C$ with $x-2$ colors and $E$ with $x-1$ colors. This gives us that $F$ must be colored with $x-3$ colors and D with $x-2$ colors.

And it gives me polynomial equal to $$x(x-1)^2(x-2)^2(x-3)$$ But according to wikipedia, coefficient next to $[x^{n-1}]$ is equal to minus number of edges. Wolfram says that $$[x^{n-1}]x(x-1)^2(x-2)^2(x-3) = -9$$ but we have clearly 8 edges here. Seems like i counted something wrong (too much?), so i'd love to hear some hints or solutions to my problem. Thank you in advance!

2

There are 2 best solutions below

3
On BEST ANSWER

The problem here is that you haven't accounted for the fact that $E$ and $B$ might have the same color, and $E$ and $C$ might have the same color.

There are cases here that need considering:

Case 1: $E$ has the same color as $B$.

In this case, there are $x$ choices for $A$; $x-1$ for $B$ and $E$; $x-2$ for $C$; $x-1$ for $D$; and $x-2$ for $F$. So, the contribution by this case is $x(x-1)^2(x-2)^2$.

Case 2: $E$ has the same color as $C$.

In this case, there are $x$ choices for $A$; $x-1$ choices for $C$ and $E$; $x-2$ for $B$; $x-2$ for $d$; and $x-1$ for $F$. So, the contribution by this case is $x(x-1)^2(x-2)^2$ as well.

Case 3: $E$, $B$, and $C$ all have different colors.

In this case, there are $x$ choices for $A$, $x-1$ for $B$, $x-2$ for $C$, and $x-3$ for $E$; given these choices, there are $x-2$ choices for $D$ and $x-2$ choices for $F$. So, the contribution by this case is $x(x-1)(x-2)^3(x-3)$.

So, all told, the chromatic polynomial for $G$ is $$ \begin{align*} P_G(x)&=2x(x-1)^2(x-2)^2+x(x-1)(x-2)^3(x-3)\\ &=x(x-1)(x-2)^2(x^2-3x+4)\\ &=x^6-8x^5+27x^4-48x^3+44x^2-16x. \end{align*} $$

5
On

Alternatively you can use Deletion-Contraction on your graph; the edge AE works well.

You can then use Complete Intersection and other standard methods (see pages 24 and 25 of my coursenotes) to get: $$P(G,x) = P(G-AE,x) - P(G/AE,x) \\ = \frac{P(C_3,x)P(C_5,x)}{P(K_2,x)} - x(x-1)(x-2)^3 \\ = (x-2)((x-1)^5 + 1 - x) - x(x-1)(x-2)^3 \\ = x(x-1)(x-2)^2 ( x^2 - 2x + 2 - (x-2) ) \\ = x(x-1)(x-2)^2 ( x^2 - 3x + 4 )\\ = x^6 - 8x^5 +27x^4 -48x^3 +44x^2 -16x $$

For $P(G/AE,x)$ we can break it into 3 triangles using Complete Intersection twice:

$$P(G/AE,x) = \frac{P(ABD,x)P(ABCF,x)}{P(K_2,x)} \\ = \frac{P(ABD,x)}{P(K_2,x)} \frac{P(ABC,x)P(ACF,x)}{P(K_2,x)} \\ = \frac{ [ x(x-1)(x-2) ]^3 } { [ x(x-1) ]^2 }\\ = x(x-1)(x-2)^3$$

However, it is easier to use the method outlined by Nicholas for such graphs made of triangles.