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$?
Graph theory: Determining $k$ from the chromatic polynomial
0
$\begingroup$
graph-theory
-
0Yeah the chromatic number, sorry I should of said! – 2012-12-07
1 Answers
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$.
-
0See also [Wikipedia](http://en.wikipedia.org/wiki/Chromatic_polynomial), last line of Section "Definition". – 2012-12-08