Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am asked the following:

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.

share|cite|improve this question
Note that math formatting works in block quotes just like it works elsewhere. – joriki Dec 4 '12 at 19:24
up vote 3 down vote accepted

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


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.

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.