Subscribe to the weekly news from TrueShelf

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

0

0

0

0

0

0

0

0

0

0