# Chromatic Polynomial

Let n be a positive integer at least 3.

The wheel W_n is the graph obtained by taking the cycle C_n, placing an additional vertex at the center, and joining it to each of the other n vertices on the rim using n more edges (spokes).

Find the chromatic polynomial for W_n.

I know that the form of a chromatic polynomial of a wheel graph looks like: $${P_w}_n(x)= x((x-2)^{n-1} - (-1)^n(x-2))$$ The equation above doesn't take into acount the "vertex at the center" as asked in the question. I am confused on how to proceeding with this problem in order to find the chromatic polynomial $W_n$ any help or guidance is welcome.

-
Note that math formatting works in block quotes just like it works elsewhere. – joriki Dec 4 '12 at 19:24

You're using a different numbering than Wikipedia; your $W_n$ is Wikipedia's $W_{n+1}$. Thus you need to substitute $n+1$ for $n$, yielding the chromatic polynomial

$$x((x-2)^n-(-1)^{n+1}(x-2))\;.$$

To find this polynomial, note that you need one colour for the centre and the remaining $x-1$ colours for the remaining vertices, which form a cycle $C_n$. The number of colourings of $C_n$ with $r$ colours is calculated in this answer, and substituting $x-1$ for $r$ and multiplying by $x$ for the number of choices for the colour of the centre yields the above polynomial.

-
I'm still a little confused, Could you expand on your answer. I tried doing the problem out and got stuck with: $$x\{(x-2)^{n-1}[\sum_{j=0}^{n-2} (-1)^{j+1}(x-2)^{-j-1} ](x-1)+ (-1)^h(x-2)(x-1)(x-3)\}$$ not sure where to go from here or if this is even right. (This is using the wikipedia notation not the questions notation) – Nick Dec 5 '12 at 17:21
@Nick: It's hard to say anything about that without knowing how you derived it. Did you follow the link? There's a complete derivation of the result there. – joriki Dec 6 '12 at 9:16
I didn't, sorry I over looked the link thanks! – Nick Dec 12 '12 at 21:17
@Nick: The chromatic polynomial of a cycle graph is also derived in the answer to this question. – bof Jan 1 '15 at 9:25

You can find a solution in this paper on page 10.

-