Subscribe to the weekly news from TrueShelf

0

Chromatic number of interval graphs

An undirected simple graph \(G = (V,E)\) is an interval graph if and only if there exists a family of intervals \({I_u}_{u\in V}\) such that \(I_u\) intersects \(I_v\) if and only if \((u,v)\in E\).

Prove that the chromatic number of an interval graph is equal to its clique number.

Related Content