Interval chromatic number of an ordered graph

Interval chromatic number X_<(H) of an ordered graph H, is the minimum number of intervals the(linearly ordered) vertex set of H can be partitioned into so that no two vertices belonging to the same interval are adjacent in H.

^[1]

Difference with Chromatic number

It is interesting about interval chromatic number that it is easily computable.Indeed, by a simple greedy algorithm one can efficiently find an optimal partition of the vertex set of H into X_<(H) independent intervals/ This is in sharp contrast with the fact that even the approximation of the usual chromatic number of graph is an NP hard task.

Let K(H) is the chromatic number of any ordered graph H. Then for any ordered graph H, X_<(H) ≥ K(H).

Reference

^ Janos Pach, Gabor Tardos,"Forbidden Pattern and Unit Distances",page 1-9,2005,ACM.

[1] Janos Pach, Gabor Tardos,"Forbidden Pattern and Unit Distances",page 1-9,2005,ACM.

[1]