Find all proper coloring of paths, cycles and wheels if a fix number of color in allowed

Question

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:

1. A path with n vertices (and n - 1 edges).
2. A cycle with n vertices (and n edges).
3. 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?

Answer 1

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}$

Answer 2

Part 1: For a path graph with $n$ vertices, the answer is $$ P(n,k)=k(k-1)^{n-1}$$ where $P(n,k)$ denotes the number of proper colorings of the path graph using $k$ colors. The first vertex can be colored in $k$ ways, and each of the other vertices can be colored in $k-1$ ways.

Part 2:Let us define $C(n,k)$ as the number of proper colorings of the cycle graph using $k$ colors. Then, we have

$$P(n,k)= C(n,k)+C(n-,k)$$

becuase for each proper coloring of a path graph there are two cases either both ends have the same color or they have different colors. Hence, the answer is

$$ C(n,k)=P(n,k)-P(n-1,k)+ P(n-2,k)- \cdots + (-1)^{n-1} C(3,k)$$

with $$C(3,k)=k(k-1)(k-2).$$

Part3: For the case of a wheel graph with $n+1$ vertices, the answer is

$$ kC(n,k-1).$$

Indeed, the centeral vertex can be colored in $k$ ways and the ones on the cycle can be colored only using the remaining $k-1$ colors.