On the interval chromatic number of proper interval graphs

A perfect graph is a graph every subgraph of which has a chromatic number equal to its clique number (Berge, 1963; Lovász, 1972). A (vertex) weighted graph is a graph with a weight function w on its vertices. An interval coloring of a weighted graph maps each vertex v to an interval of size w(v) such that the intervals corresponding to adjacent vertices do not intersect. The size of a coloring is the total size of the union of these intervals. The minimum possible size of an interval coloring of a given weighted graph is its interval chromatic number. The clique number of a weighted graph is the maximum weight of a clique in it. Clearly, the interval chromatic number of a weighted graph is at least its clique number. A graph is superperfect if for every weight function on its vertices, the chromatic number of the weighted graph is equal to its clique number (Hoffman, 1974). It is known that determining the interval chromatic number of a given interval graph is NP  -Complete, implying that interval graphs are not included in the family of superperfect graphs (Golumbic, 2004). The question whether these results hold for simple graph families is open since then. We answer this question affirmatively for proper interval graphs for which most investigated problems are polynomial (http://www.graphclasses.org/classes/gc_298.html). Specifically, we show that determining the interval chromatic number of a proper interval graph is NP  -Complete in the strong sense. We present a simple 2-approximation algorithm for this special case, whereas the best known approximation algorithm for interval graphs is a (2+ϵ)-approximation (Buchsbaum et al., 2004).