0
$\begingroup$

I know how to work out the chromatic polynomial of a graph and I can work out what $k$ would be by looking at the graph. Maybe I'm just being silly, but if you were given just the chromatic polynomial say: $ k(k-1)^2 (k-2) $ can you just look at that and tell that the chromatic number of $G$ is $3$?

  • 0
    Yeah the chromatic number, sorry I should of said!2012-12-07

1 Answers 1

1

If $p(k)$ is the chromatic polynomial of $G$, then the chromatic number of $G$ is the smallest non-negative integer $k_0$ such that $p(k_0)>0$.

In this case, you can clearly see that $p(0)=p(1)=p(2)=0$, while $p(3)\neq 0$, so the chromatic number must be $3$.

  • 0
    See also [Wikipedia](http://en.wikipedia.org/wiki/Chromatic_polynomial), last line of Section "Definition".2012-12-08