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.

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 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|cite|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
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|cite|improve this answer
Hmm, I found this when I googled what Yuval suggested-… 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.

share|cite|improve this answer

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.