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
    @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.