7
$\begingroup$

I need to get the chromatic polynomial for the complete bipartite graph: $K_{2,3}$

Im using the Fundamental Reduction Theorem, and the picture below shows mi attempt to it.

graph

I omitted vertex names because is just a small graph.

With this procedure i get: $P(K_{2,3},x)=\frac{C_4.K_2}{K_1}-\frac{K_3.K_3}{K_2}$

Here $C_4$ is a cycle lenght 4 joined to a complete graph lenght 2 just by one vertex. And is well known that: $P(C_4,x)=x(x-1)(x^2-3x+3)$.

I think im doing well, but the final result is: $x (-3 x^3+12 x^2-16 x+7)$ and is not correct.

The correct result is supposed to be: $x (x-1) (x^3-5 x^2+10 x-7)$

I think im close, but evidently im failing at some point.

$\endgroup$

1 Answer 1

8
$\begingroup$

The correct answer is $x (x-1) (x^3-5 x^2+10 x-7)$. Here is another argument to prove it:

In any coloring of $K_{2,3}$ the two vertices in the first part will have either the same color or two different colors. So, in the first case, there are $x$ colors to choose the same color and $x-1$ colors to choose from to color the remaining three vertices. Thus there are $x(x-1)^3$ colorings of this first kind.

In the second case, there $x(x-1)$ ways to color the two vertices with different colors and we are left with $x-2$ colors to choose from to color the remaining three vertices. Thus, there are $x(x-1)(x-2)^3$ colorings of this second kind.

So, in total we have: $x(x-1)^3 + x(x-1)(x-2)^3$ colorings. After simplification you get your answer.

** Edit:

Also your method wields the same result:

So $P(K_{2,3},x)=\frac{P(C_4, x).P(K_2, x)}{P(K_1, x)}-\frac{P(K_3, x).P(K_3, x)}{P(K_2, x)}$

and we have:

$P(C_4,x)=x(x-1)(x^2-3x+3)$,

$P(K_3, x)= x(x-1)(x-2)$,

$P(K_2, x)= x(x-1)$

and $P(K_1, x)= x$

So, $P(K_{2,3},x)=\frac{x(x-1)(x^2-3x+3).x(x-1)}{x}-\frac{(x(x-1)(x-2))^2}{x(x-1)}$

$P(K_{2,3},x)=x(x-1)^2(x^2-3x+3)- x(x-1)(x-2)^2$

$P(K_{2,3},x)=x(x-1)[(x-1)(x^2-3x+3)- (x-2)^2 ]$

$P(K_{2,3},x)=x(x-1)[(x-1)(x^2-3x+3)- (x-2)^2 ]$

This will give you the correct answer.

$\endgroup$
7
  • $\begingroup$ Thanks. I know this method too. But i need to prove it with the fundamental reduction theorem. Its a small graph, it cannot be so difficult. $\endgroup$
    – Wyvern666
    Feb 14, 2014 at 23:28
  • $\begingroup$ Even your method wield the correct answer. $\endgroup$
    – hbm
    Feb 14, 2014 at 23:34
  • $\begingroup$ Sorry, i dont see how. $\endgroup$
    – Wyvern666
    Feb 14, 2014 at 23:37
  • 2
    $\begingroup$ I will edit my answer to explain how. $\endgroup$
    – hbm
    Feb 14, 2014 at 23:39
  • $\begingroup$ Ok, i fell very stupid. I need a break. Thanks! $\endgroup$
    – Wyvern666
    Feb 15, 2014 at 0:12

You must log in to answer this question.

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