[Math] Chromatic Polynomial of Ladder Graph

Question

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?

Answer 1

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.