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!
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.