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 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$?

share|cite|improve this question
What is $k$? It's not clear from the question. – Thomas Andrews Dec 7 '12 at 14:51
Yes, is it supposed to be chromatic number? – Simon Hayward Dec 7 '12 at 15:01
Yeah the chromatic number, sorry I should of said! – Jack Dec 7 '12 at 15:02
up vote 1 down vote accepted

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

share|cite|improve this answer
Thank you! My lecture notes have totally just skipped that – Jack Dec 7 '12 at 15:26
See also Wikipedia, last line of Section "Definition". – Hendrik Jan Dec 8 '12 at 11:57

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.