1
$\begingroup$

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.

  • 0
    From [Wikipedia](http://en.wikipedia.org/wiki/Clique_number#Mathematics), '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.2012-07-05

2 Answers 2

0

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.

  • 0
    Hmm, I found this when I googled what Yuval suggested- http://webcourse.cs.technion.ac.il/234247/Spring2004/ho/WCFiles/GreedyAlgorithms.pdf as a corollary fo theorem 2. I too would like to see that written explicitly as a proof for $\chi(G)= \omega(G)$.2012-07-06
  • 0
    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](http://meta.stackexchange.com/questions/19756/how-do-comments-work/19757#19757). 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](http://meta.stackexchange.com/questions/7237/how-does-reputation-work/7238#7238).2012-07-06
  • 0
    @Aria, I believe it is better if Layla and you worked it out yourselves. All you need to know is this greedy algorithm.2012-07-06
0

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.