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

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?

• Yes, and it goes by the name of "deletion-contraction". Let $G$ be a graph, let $e$ be an edge in $G$, let $u,v$ be the vertices joined by $e$. Let $H$ be the graph you get by deleting the edge $e$, and let I be the graph you get by replacing $u$ and $v$ by a single new vertex $w$ (adjacent to all the neighbors of $u$ and all the neighbors of $v$). Then the number of ways to color $G$ is the number of ways to color $H$ minus the number of ways to color $I$. Dec 6, 2020 at 4:56
• Making any progress? Dec 7, 2020 at 12:32
• @GerryMyerson Hi Gerry! My thoughts are as follows: denote the possible paths of n vertices as Pn, then the number of colors Cn can have is Pn - Pn-1 + Pn-2 ... Is it correct? Dec 8, 2020 at 2:15
• OK, but, where does that alternating sum end? Dec 8, 2020 at 9:04
• It ends at (-1)^k K3, where we can compute the colors, right? Thanks for all the follow-ups man! Dec 8, 2020 at 14:25

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

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.