Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
2  
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

1 Answer 1

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

 
discard

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.