Find the chromatic polynomials of $K_{2,s}$

1.4k Views Asked by At

I'm working in the following graph theory excercise:

Find the chromatic polynomials of $K_{2,s}$

Starting from this generalization:

Bipartite graph of the way K_2,n

I have two cases:

Case 1: $x_1$ and $x_2$ are colored different so $x_1$ would have $\lambda$ options to be colored and $x_2$ would have $(\lambda-1)$ options to be colored, then $y_1,y_2,y_3,y_4,y_5$ would have $(\lambda - 2)$ options to be colored.

Case 2: $x_1$ and $x_2$ are colored in the same color so $x_1$ would have $\lambda$ options to be colored and $x_2$ would have $\lambda$ options to be colored, then $y_1,y_2,y_3,y_4,y_5$ would have $(\lambda - 1)$ options to be colored.

After this process I'm using the addition principle for combining mutually exclusive cases, so I get:

$$P_G(\lambda) = \lambda(\lambda - 1)(\lambda - 2)^s + \lambda\lambda(\lambda - 1)^s $$

I'm not sure about my result in the case 2, is it correct $\lambda\lambda(\lambda - 1)^s$? I'm not sure about those two $\lambda$ multiplying. Thanks in advance for any hint or help.

Updated Correct Answer is : $$P_G(\lambda) = \lambda(\lambda - 1)(\lambda - 2)^s + \lambda(\lambda - 1)^s $$

1

There are 1 best solutions below

0
On BEST ANSWER

There is one little error with your chromatic polynomial: for case 2, because $x_1$ and $x_2$ are made to be the same colour, there are only $\lambda$ choices for both vertices, not $\lambda^2$ (which is in fact the number of ways to colour $x_1$ and $x_2$ without restrictions). Thus the $\lambda\lambda$ should be just $\lambda$; selecting a colour for either $x_i$ in case 2 determines the other $x_i$'s colour.

Other than that, your polynomial is correct.