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?
Best Answer
Now I proceed to answer 2 and 3.
By the power of deletion-contraction theorem, note that the proper coloring of a cycle (with n vertices) is reduced to the difference between proper coloring of a path (whose proper coloring we have calculated in 1), and the graph that we merge two arbitrary vertices together, which, when n larger than 3, is also a cycle.
We then apply deletion-contraction theorem again on the smaller cycle to derive a path of (n-1) vertices and a cycle of (n-2) vertices. Repeat this to derive the formula $ P_n - P_{n-1} + P_{n-2} + ... + (-1)^n K_3 $, where P denote the coloring of the paths and K denote the coloring of the complete graph.
For the proper coloring of the wheel graph, notice that a wheel graph is a cycle with an additional vertex connecting to every other vertice. We can color the cycle first, and then take a look at the vertex left. If the colors we had in hand are more than the vertex needs to be coloring, then we can freely choose the unused colors. It follows that the proper coloring of a wheel graph with (n+1) vertices is $(k-n)*C_{n}$