Recall that a proper vertex coloring is an assignment of a color to each vertex in a graph such that adjacent vertices receive different colors. For a fix n and fix color choices k, find the number of proper vertex colorings for the following graph:
- A path with n vertices (and n - 1 edges).
- A cycle with n vertices (and n edges).
- A wheel graph which has n + l vertices.
Now, 1 is rather simpler. I'm trying to attempt this problem by considering a recurrence relation: if we have already known the proper coloring of a path with (n-1) vertices, we need only multiply it with (k-1) colors to get all the proper coloring with n vertices.
But 2 and 3 seems to need a little bit more thinking. Are there any theorems related to it?