Chromatic polynomial of a square

ignougroup
Problem Detail: Consider a square, ABCD. Intuitively it seemed to me that its chromatic polynomial is $lambda(lambda – 1)(lambda – 1)(lambda – 2)$ where there are $lambda$ colours available.. That is there are $lambda$ ways in which a colour for A can be picked, there are $lambda – 1$ ways for colours for B and D to be picked(B and D are adjacent to A) and $lambda – 2$ ways for colours for C to be picked. However using the decomposition theorem (slide 47, Example 11.33) and decomposing the square into a path of length 3 and a triangle, shows that my initial reasoning is wrong. Could you tell me where I am going wrong with my thinking.

Asked By : Abhijith Madhav

Answered By : Abhijith Madhav

The answer by Nicholas above and this one helped me see the flaw in my thinking. I thought of elaborating more specifically upon Nicholas’,

You must remember that the vertices diagonal from one another can be colored the same

and also obtain the chromatic polynomial by adjusting for my wrong reasoning. I had initially figured that there are $lambda – 2$ ways of picking colors for C. The “-2” accounted for the colors being different from that of B and D. What I did not think about is that B and D can have the same colors in which case there would be just $lambda – 1$ way of picking colors for C. Thus $P(ABCD, lambda)$ = Number of ways of properly coloring ABCD when B and D are of the same color + Number of ways of properly coloring ABCD when B and D are colored differently
= $λ(λ−1)(1)(λ−1) + λ(λ−1)(λ−2)(λ−2)$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/4758