2
$\begingroup$

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.

  • 0
    Note that math formatting works in block quotes just like it works elsewhere.2012-12-04

2 Answers 2

3

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.

  • 0
    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)2012-12-05
  • 0
    @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.2012-12-06
  • 0
    I didn't, sorry I over looked the link thanks!2012-12-12
  • 0
    @Nick: The chromatic polynomial of a cycle graph is also derived in the answer to [this question](http://math.stackexchange.com/questions/1052591/prove-chromatic-polynomial-of-n-cycle).2015-01-01
0

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