Thread: Interval graph

Prove that if G is a complement of an interval graph (http://en.wikipedia.org/wiki/Interval_graph):

χ(G)=ω(G)
where χ(G): chromatic number; ω(G): clique number

Thank you in advance!

We know that χ(G)>ω(G) is alwasys true for any graphs. So to prove the equality you just have to prove that χ(G)<=(G) is true as well. So you should admit that your graph is ω-colourable, it is enough to show an appropriate colouring using ω colours.
It is useful to think over what a clique means in that G complement graph and which vertices are in the same colour class.
clique: vertices that represents disjoint intervals
vertices in the same colour class: they represents intervals that have a common point (have a common intersection)

I hope that with the help of these hints you can solve the problem.

Thanks a lot, but I am afraid I can't solve the problem.