Chromatic Polynomial of Ladder Graph Hey guys I am trying to understand the formula for the chromatic polynomial of a ladder graph.
$$k(k-1)(k^2-3k+3)^{n-1}$$
Can you guys help me understand how we get to this?
 A: Use deletion-contraction as described in this Wikipedia entry. Let the deletion edge $(u,v)$ be the edge at the top of the ladder and let $G_n$ be the ladder graph. Then we have
$$P(G_n,k) = P(G_n-uv,k)-P(G_n/uv,k).$$
But $G_n-uv$ is a ladder graph of height $n-1$ with two free standing vertices at the top. These can each take any one of $k-1$ colors, since they only need to differ in color from the vertex where they are attached to the ladder and there is no edge between them. Hence
$$P(G_n-uv,k) = (k-1)^2 P(G_{n-1},k).$$
The graph $G_n/uv$ has a vertex attached to the top two vertices to form a triangle. This vertex must differ in color from the two vertices where it is attached to the ladder. Hence
$$P(G_n/uv,k) = (k-2) P(G_{n-1},k).$$
We conclude that
$$P(G_n,k) = ((k-1)^2 - (k-2)) P(G_{n-1},k) = (k^2-3k+3) P(G_{n-1},k).$$ Now just use the fact that the ladder graph of height one is a path on two vertices and has $k(k-1)$ colorings.
A: See here http://exwiki.org/mw/index.php?title=The_chromatic_polynomial_of_the_ladder_graph 
The idea is to use the fact that if $G$ has subgraphs $H_1,H_2$ such that $H_1 \cup H_2 = G$ and $H_1 \cap H_2 = K_n$ then $$P(G,k) = \frac{(H_1,k)P(H_2,k)}{P(K_n,k)}$$
This can be used to make a straightforward recurrence for $P(L_n,k)$
A: We can do this inductively. when $n=1$ this is just $K_2$, so the formula clearly holds. Then suppose it is true for $n-1$ and show that for $n$ the formula is $P(G_n,k)=(k^2-3k+3)*P(G_{n-1},k)$. Name the two points added as $u,v$ respectively. Then by deletion contraction, $P(G_n,k)=P(G_n-uv,k)-P(G_n/uv)$; in the first of these new polynomials, it is the same as $G_{n-1}$ with two pendant vertices added; these can be all but one color, the one they are adjacent to. In the second we now have a point appended onto $G_{n-1}$. This can be all but two colors. Then we have $P(G_{n-1},k)((k-1)^2-(k-2))=P(G_{n-1},k)(k^2-3k+3)$. Then inductively, the formula holds.
A: Take the point of the far bottom left and start colouring from there. there are k options for that colour (suppose we colour it with colour a). Now go to the one to the bottom right, there are k-1 options for the colour of that element(suppose we colour it with colour b). Now take  a look at all the pairs above that one. how many pairs are there available for the two vertices above? 
one choice is to take the one on the left with a and the one on the right with b.(1 way) 
the other is to colour the one in the left with b and the one in the right with a colour different from a or the one to the left of it: ($k-2$ ways)
another one is to colour the one on the right with a and the one in the left with a colour different from b ($k-2$ options)
and the last option is to colour the ones of top with colours different to the ones above $(k-2)(k-3)=k^2-5k+6$
add them all up to get $k^2-3k+3$ ways to colour each pair above.
using there are n-2 such pairs and the fundamental counting principle and the fact there are k options for bottom left and k-1 for bottom right we know there are $k(k-1)(k^2-3k+3)^{n-1}$ colourings as desired.
