# Clique number and chromatic number equal for interval graph-proof

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.

-
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

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.

-
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

This follows immediately from the fact that interval graphs are perfect (conversely, the fact that interval graphs are perfect follows from the clique number and chromatic number being equal).

I believe Cormen et al contains a greedy algorithm for interval graph coloring.

-