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 cannot seem to find a proof anywhere for the following lemma: Show that for any interval graph, the chromatic number is equal to the clique number.

The lemma is used everywhere but I cannot find a proof. Could you show me the proof, rather than a hint? That would be much appreciated.

share|improve this question
    
From Wikipedia, 'An interval graph is a graph whose maximal cliques can be ordered in such a way that, for each vertex v, the cliques containing v are consecutive in the ordering.' Don't know the answer but that seems to be the connection. –  Eugene Shvarts Jul 5 '12 at 22:38

1 Answer 1

up vote 0 down vote accepted

Hint: Look up on the web the optimal greedy coloring algorithm for interval graphs. It provides an algorithmic proof for the lemma.

Another hint: If the graph does not contain a $(k+1)$-clique, then the algorithm will color it with $k$ colors. This shows that $\chi(G) \leq \omega(G)$. The reverse inequality is always true.

share|improve this answer
    
Hmm, I found this when I googled what Yuval suggested- webcourse.cs.technion.ac.il/234247/Spring2004/ho/WCFiles/… as a corollary fo theorem 2. I too would like to see that written explicitly as a proof for $\chi(G)= \omega(G)$. –  Aria Fitzpatrick Jul 6 '12 at 2:45
    
Aria, I have converted your answer to a comment. Answers should be reserved for posts that answer the question; but because you do not have 50 reputation points yet, you can only comment on your own questions and answers. So, you didn't do anything wrong; the "add comment" button will only appear for you once you gain 50 points. Here is an explanation of reputation points. –  Zev Chonoles Jul 6 '12 at 5:00
    
@Aria, I believe it is better if Layla and you worked it out yourselves. All you need to know is this greedy algorithm. –  Yuval Filmus Jul 6 '12 at 5:53

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.