Chromatic Polynomials of Wheel Graphs

Coloring a Wheel from Its Hub

A wheel has a central hub joined to every vertex of a rim cycle. To color it properly, first choose a color for the hub. Each rim vertex is then forbidden from using that color, so the rim must be colored as a cycle using the remaining colors. This separates the counting into two parts: the number of hub choices and the number of colorings of a cycle.

All graphs in this tutorial are finite and simple. A proper coloring with $k$ colors assigns one of $k$ colors to each vertex so that adjacent vertices receive different colors. The chromatic polynomial $P(G,x)$ is the polynomial whose value at each nonnegative integer $k$ is the number of proper colorings of $G$ with $k$ available colors.

Definition: For $n\ge3$, the wheel $W_n$ consists of a rim cycle $C_n$ and one additional vertex $h$, called the hub, joined to every rim vertex. Thus $W_n$ has $n+1$ vertices. In particular, the hub is not counted among the $n$ rim vertices.

We will use the chromatic polynomial of a cycle. The key detail is that a cycle coloring must satisfy the extra condition that its last vertex differs in color from its first. The following count makes that condition explicit.

Counting Colorings of a Cycle

Lemma: For $n\ge3$, the number of proper colorings of $C_n$ with $q$ available colors is $(q-1)^n+(-1)^n(q-1)$, for every nonnegative integer $q$.

Proof. First suppose $q\ge1$, and fix a color for the first vertex of a path on $n$ vertices. Let $A_n$ be the number of proper colorings of that path for which the last vertex has the fixed color, and let $B_n$ be the number for which the last vertex has a different color. When a new vertex is appended, it has to differ from the old last vertex. Therefore $A_{n+1}=B_n$: to end with the fixed color, the old last vertex must differ from it, and the new vertex then has exactly one choice. To end with a color different from the fixed color, there are $q-1$ choices if the old last vertex has the fixed color, and $q-2$ choices if it already differs. Hence \[ B_{n+1}=(q-1)A_n+(q-2)B_n. \] We have $B_1=0$ and $B_2=q-1$. Since $A_n=B_{n-1}$ for $n\ge2$, the recurrence becomes $B_{n+1}=(q-1)B_{n-1}+(q-2)B_n$. For $n\ge1$, its solution is \[ B_n=\frac{(q-1)^n+(-1)^n(q-1)}{q}. \] Indeed, this expression gives $B_1=0$ and $B_2=q-1$; both terms satisfy the recurrence because their respective bases $q-1$ and $-1$ satisfy $r^2-(q-2)r-(q-1)=0$. A cycle coloring is a path coloring whose final vertex differs from its first, so its count is $qB_n=(q-1)^n+(-1)^n(q-1)$. If $q=0$, there are no colorings of the nonempty cycle, and the displayed expression is $(-1)^n+(-1)^n(-1)=0$, as required. $\square$

The lemma counts labeled color choices: colors are available options, not names for color classes to be identified with one another. It also includes $q=1$, where the cycle cannot be properly colored. We now apply it to the rim after the hub’s color has been chosen.

The Chromatic Polynomial of a Wheel

Theorem: For $n\ge3$, the chromatic polynomial of the wheel $W_n$ is $$ P(W_n,x)=x\bigl((x-2)^n+(-1)^n(x-2)\bigr). $$

Proof. First let $k\ge2$ be an integer number of available colors. The hub can be colored in $k$ ways. Once its color is chosen, none of the rim vertices may use it. The rim is a copy of $C_n$, with $k-1$ colors available. By the lemma, the number of ways to color it is \[ (k-2)^n+(-1)^n(k-2). \] Multiplying by the $k$ hub choices gives \[ P(W_n,k)=k\bigl((k-2)^n+(-1)^n(k-2)\bigr). \] For $k=1$, the wheel has no proper coloring: the hub forces every rim vertex to use the only color, contradicting the rim edges. The formula also gives $1\bigl((-1)^n+(-1)^n(-1)\bigr)=0$. For $k=0$, there are no colorings of this nonempty graph, and the formula is zero because of its leading factor $k$. Thus the formula agrees with the coloring count for every nonnegative integer $k$. Since chromatic polynomials agreeing at infinitely many integers are equal, it is the stated polynomial. $\square$

The factor $x$ records the hub choices. The remaining factor is the cycle-coloring count with $x-1$ available colors, written after substituting $x-1$ for $q$ in the cycle formula. The expression is a polynomial even though this counting explanation starts with integer numbers of colors.

Worked Example: The Smallest Wheel

For $n=3$, the rim is a triangle, and the hub is adjacent to all three rim vertices. Thus every pair of vertices is adjacent: $W_3$ is $K_4$. The wheel formula gives $$ P(W_3,x)=x\bigl((x-2)^3-(x-2)\bigr). $$ Factor the difference of cubes in the form $a^3-a=a(a-1)(a+1)$, with $a=x-2$: $$ P(W_3,x)=x(x-2)(x-3)(x-1). $$ This agrees with the complete-graph count: the four vertices of $K_4$ must receive four distinct colors, giving $x(x-1)(x-2)(x-3)$.

For a numerical check, take $k=4$. The formula gives $4((4-2)^3-(4-2))=4(8-2)=24$. Directly, $K_4$ uses four distinct colors, so the count is $4\cdot3\cdot2\cdot1=24$. If $k=3$, the formula gives $3(1-1)=0$, consistent with the need for four distinct colors.

Worked Example: A Wheel with a Square Rim

Let $W_4$ have rim vertices $1,2,3,4$ and hub $h$. Its edge set is $\{12,23,34,41,h1,h2,h3,h4\}$. The formula gives $$ P(W_4,x)=x\bigl((x-2)^4+(x-2)\bigr). $$ At $k=3$, there are $3$ hub choices. The rim then has $2$ colors available. A square has exactly $2$ proper colorings with two colors: once the color at vertex $1$ is chosen, the colors at $2,3,4$ are forced to alternate. Thus the total is $3\cdot2=6$. Substitution gives $3((3-2)^4+(3-2))=3(1+1)=6$.

At $k=4$, the hub has $4$ choices and the rim has $3$ colors. Fixing the color of rim vertex $1$, the path recurrence in the lemma gives the counts $A_1=1,B_1=0$, then $A_2=0,B_2=2$, then $A_3=2,B_3=2$, and then $A_4=2,B_4=6$. Therefore the square has $3\cdot6=18$ colorings: there are $3$ choices for the first rim color and $6$ choices whose final color differs from it. Including the hub gives $4\cdot18=72$. The wheel formula gives $4((4-2)^4+(4-2))=4(16+2)=72$.

Check: The direct rim count at $k=4$ is $18$, and the formula’s rim factor is $(4-2)^4+(4-2)=16+2=18$. Multiplication by the $4$ hub choices gives $72$ by both counts.

Worked Example: A Wheel with a Pentagonal Rim

Let $W_5$ have rim vertices $1,2,3,4,5$ and hub $h$, with edges $12,23,34,45,51,h1,h2,h3,h4,h5$. Its chromatic polynomial is $$ P(W_5,x)=x\bigl((x-2)^5-(x-2)\bigr). $$ With $k=3$, the hub leaves $2$ colors for the rim. A cycle colored with two colors must alternate, and after an odd number of edges the color would have to change back to its starting color while also differing from it. So the pentagonal rim has no such coloring. The formula confirms this: $3((3-2)^5-(3-2))=3(1-1)=0$.

With $k=4$, the rim has $3$ available colors. To check the rim count directly, fix the first rim color. For $q=3$, the recurrence gives $A_1=1,B_1=0$, $A_2=0,B_2=2$, $A_3=2,B_3=2$, $A_4=2,B_4=6$, and $A_5=6,B_5=10$. Thus there are $3\cdot10=30$ pentagon colorings: $3$ choices for the first color and $10$ choices ending in a different color. The hub has $4$ choices, so the wheel has $4\cdot30=120$ colorings. Substitution gives $4((4-2)^5-(4-2))=4(32-2)=120$.

Check: The direct rim count is $30$, and the formula’s rim factor is $2^5-2=32-2=30$. After multiplying by $4$ hub choices, both methods give $120$.

Common Mistake: Forgetting the Forbidden Hub Color

After choosing the hub color, the rim does not have all $k$ colors available: every rim vertex is adjacent to the hub, so that color is forbidden throughout the rim. The correct substitution in the cycle formula is $q=k-1$, not $q=k$.

For example, using $k$ instead of $k-1$ would incorrectly give $P(W_4,3)=3((3-1)^4+(3-1))=3(16+2)=54$. But after the hub is colored, the square has only $2$ colors available and exactly $2$ proper rim colorings. The correct total is $3\cdot2=6$, also obtained from $3((3-2)^4+(3-2))=6$. The erroneous calculation overcounts because it allows rim vertices to use the hub’s color.

The parity of the rim length controls the sign in the formula. For an even rim, the cycle expression has a plus sign; for an odd rim, it has a minus sign. This sign comes from requiring the last rim vertex to differ from the first, not from an extra choice at the hub.

Check Your Understanding

Use the definition of the wheel and the cycle-coloring count to answer these questions.

Write the vertex and edge sets of $W_3$, and explain why it is $K_4$.
Evaluate $P(W_6,3)$. Interpret the result in terms of coloring the rim after the hub is colored.
For $W_5$, how many proper colorings are there with $4$ colors? Show the hub count and the rim count separately.
Explain why substituting $q=x-1$, rather than $q=x$, into the cycle polynomial gives the wheel formula.
Use the formula to find $P(W_4,2)$, and explain why the answer is consistent with the wheel’s edges.

Chromatic Polynomials of Wheel Graphs

What You'll Learn