Coloring points on an n-gon

Given an $n$-sided polygon, how many ways can you color the vertices using $k$ colors so that no two adjacent vertices have the same color?

(Inspired by 2011 AMC 12 A #16 – I'm able to do this for small cases but not in general.)

-

Here are two ways to do the problem, both of which use graph theory. The problem is equivalent to counting the number of closed walks of length $n$ on the complete graph $K_k$ on $k$ vertices. The number of closed walks of length $n$ on a graph $G$ with adjacency matrix $A$ is given by $\text{tr } A^n = \sum_{i=1}^k \lambda_i^n$ where $\lambda_i$ are the eigenvalues of $A$.

So it suffices to compute the eigenvalues of the adjacency matrix of $K_k$. This is a nice exercise, but for the sake of completeness I will tell you that they are $k-1, -1, -1, ...$. So the final answer is

$$(k-1)^n + (k-1)(-1)^n.$$

The second method is to observe that the problem is equivalent to computing the chromatic polynomial of the cyclic graph $C_n$. This can be done by induction and the deletion-contraction recurrence, and you get the same answer.

Note that these two solutions generalize in different directions. The first solution suggests a generalization of the problem where you replace $K_k$ with a more complicated graph, whereas the second solution suggests a generalization of the problem where you replace $C_n$ with a more complicated graph. Both problems are in turn special cases of the following problem.

Definition: Let $G, H$ be two (undirected, simple) graphs. A morphism $f : G \to H$ is a function $f : V_G \to V_H$ sending vertices of $G$ to vertices of $H$ such that, if $u, v \in G$ are connected by an edge, then $f(u), f(v)$ are also connected by an edge.

Problem: How many morphisms are there from a given graph $G$ to a given graph $H$?

The walk problem corresponds to letting $G = C_n$ and letting $H$ be arbitrary, while the coloring problem corresponds to letting $H = K_k$ and letting $G$ be arbitrary. Both of these are very special cases. The general problem is interesting; I have no idea what's known about it.

-
Perfect, exactly what I was looking for! – Ben Alpert Feb 13 '11 at 1:17

Do you know about the chromatic polynomial? That has a simple skein formula which can be easily calculated for n-gons. It is a polynomial in k, the number of possible colorings.

-
Thanks; I'm accepting Qiaochu's answer because it's more complete (and also was a few seconds before yours). – Ben Alpert Feb 13 '11 at 1:16
Yes Qiaochu beat me to it! – Grumpy Parsnip Feb 13 '11 at 2:20