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 wa$y$ that, for each vertex v, the cl$i$ques 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
    @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.