Finding the Chromatic Polynomial for the wheel graph $W_5$

Let $G$ be a graph and let $k \in N$. The chromatic polynomial $P_G(k)$ is the number of distinct $k$-colourings if the vertices of G.

Standard results for chromatic polynomials:

1) $G = N_n$, $P_G(k) = k^n$ (Null graphs with $n$ vertices)

2) $G = K_n$, $P_G(k) = \frac{k!}{(k-n)!}$ (Complete graph with $n$ vertices)

3) When G is a tree with $n$ vertices, $P_G(k) = k(k-1)^{n-1}$

4) $G = C_n$ (for $n \geq 3$), $\quad P_G(k) = (k-1)^n +(-1)^n(k-1)$. (Cycle graph with $n$ vertices)

Given these standard results I could be asked to find the chromatic polynomial of the Wheel graph $W_n$. Where $W_n$ is defined to be the graph formed by joining each vertex of $C_{n-1}$ to one more vertex.

I have found a proposition:

Let $G$ be a simple graph with $n$ vertices and $m$ edges.

For each edge $e$ of $G$, $P_G(k) = P_{G-e}(k) - P_{G\backslash e}(k)$

Using this result to decompose $W_5$:

The chromatic polynomial of $W_5$ is equal to the CP of ($W_5$ minus and edge) - the CP of $W_5$ with the middle vertex contracted to one of the vertices of $C_4$. As I believe the chromatic polynomial is not affected by double edges I can remove all the multiple edges from $W_5$ with the middle vertex contracted to one of the vertices of $C_4$ and hence I get $C_4$.

Continuing the same method as above for $W_5$ minus 2 edges...

I iterated this until my calculation reduced to the CP of $C_4 \cup N_1$ - CP of $C_4$.

Adding all the elements together I got the following:

$$C_4 \cup N_1 - 4 C_4$$

Also, if $G$ is disconnected then $P_G(k)$ is the product of the chromatic polynomials of all the components.

Given the standard results and the above statement I thought that

$P_{W_5}(k) = k\times P_{C_4}(k) - 4P_{C_4}(k)$

$P_{W_5}(k) = (k-4)\times P_{C_4}(k)$

$P_{W_5}(k) = (k-4)\times \left[(k-1)^4 +(-1)^4(k-1)\right]$

$P_{W_5}(k) = (k-4)\times \left[(k-1)^4 +(k-1)\right]$

$P_{W_5}(k) = k^5 - 8k^4 +22k^3-27k^2+12k$

Which is not even close to the formula I found here : Wolfram Mathworld

$$P_{W_n}(k) = k\left[(k-2)^{n-1} - (-1)^n(k-2)\right]$$

$$P_{W_5}(k) = k\left[(k-2)^{4} - (k-2)\right] = k^5 - 8k^4 +24k^3-33k^2+18k$$

Could anyone please point out where I went wrong and give me some intuition how to solve this type of problems in general? Any resources where I could find worked out examples?

1 Answer

The correct answer is $k((k-2)^4+(-1)^4 (k-2)) = k^5-8k^4+24k^3-31k+14k = k(k-1)(k-2)(k^2-5k+7)$