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!

Printable View

- February 13th 2011, 08:55 AMzadirInterval 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! - February 14th 2011, 09:51 AMdoug
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. - February 14th 2011, 10:42 AMzadir
Thanks a lot, but I am afraid I can't solve the problem.