I am going through some questions in the "Bondy,Murty - Graph Theory with applications" book, and I have stumbled upon the following question:
calculate the Chromatic Polynomial of the following graph :
I figured I need to use the recursive method, meaning to rid one of the edges, but I can't figure out which way I should go about it.
The only way I see to solve this is repeating that method several times(which I did and took a while...) ,
but is there an easier way to solve it that I am missing?
1 Answer
Hmm. The chromatic polynomial, if I remember right, is a formula for the number of ways to color the graph (properly) given a supply of $x$ colors? Your graph has only $6$ vertices; that should be small enough to figure out by hand without knowing anything. Let's see. The top and bottom vertices either get the same color or different colors; let's count the two cases separately, and add.
Top and bottom vertices same color: $x$ ways to color the top and bottom; then $(x-1)(x-2)$ ways to color the two vertices on the left; likewise $(x-1)(x-2)$ ways for the two vertices on the right; so $x(x-1)^2(x-2)^2$ ways.
Top and bottom vertices different colors: $x(x-1)$ ways to color the top and bottom vertices; then $(x-2)(x-3)$ ways to color the vertices on the left, same on the right, so $x(x-1)(x-2)^2(x-3)^2$ ways.
Add: $$x(x-1)^2(x-2)^2+x(x-1)(x-2)^2(x-3)^2=x(x-1)(x-2)^2[(x-1)+(x-3)^2=x(x-1)(x-2)^2(x^2-5x+8).$$ Is that the right answer?
