On the sum coloring problem on interval graphs

In this paper we study the following Np-complete problem: given an interval graph G = (V, E), find a node p-coloring (V-1, V-2, ..., V-p) such that th e cost xi((V-1, V-2, ..., V-p)) = Sigma(i=1)(p) i/V-i/ is minimal, where (V 1, Vr,..., Vp) denotes a partition of V whose subsets are ordered by noninc reasing cardinality. We present an O(m chi(G) + n log n) time epsilon-appro ximate algorithm (epsilon < 2) to solve the problem, where n, m, and chi(G) are the number of nodes of the interval graph, its number of cliques, and its chromatic number, respectively. The algorithm is shown to solve the pro blem exactly on some classes of interval graphs, namely, the proper and the containment interval graphs, and the intersection graphs of sets of "short " intervals. The problem of determining the minimum number of colors needed to achieve the minimum xi((V-1, V-2, ..., V-p)) over all p-colorings of G is also addressed.