A Linear Time Approximation Algorithm for Interval Coloring on Proper Interval Graphs

Given a set of intervals on the real line, an interval graph is de®ned by a set of vertices associated to the intervals with edges between two vertices when the corresponding intervals overlap. If no interval properly contains another, we have a proper interval graph. When weights are associated to vertices, the interval coloring problem on a graph consists in assigning to each vertex a number of consecutive colors equal to the weight, such that adjacent vertices do not share any color and the total number of used colors is minimized. In this paper, we prove that this optimization problem on proper interval graphs is NP-hard. We give a linear time 2-approximation algorithm for it, and show that the bound is tight. Moreover, by exploiting the particular problem representation, the structure of the provided solutions are guaranteed to remain 2-approximated for any vertex weight function.