Sum coloring and interval graphs: a tight upper bound for the minimum number of colors

The SUM COLORING problem consists of assigning a color c(vi) E Z(+) to each vertex vi E V of a graph G = (VE) so that adjacent nodes have different colors and the sum of the c(vi)'s over all vertices vi E V is minimized. In this note we prove that the number of colors required to attain a minimum valued sum on arbitrary interval graphs does not exceed min{n; 2chi(G) - 1}. Examples from the papers [Discrete Math. 174 (1999) 125; Algorithmica 23 (1999) 109] show that the bound is tight. (C) 2003 Elsevier B.V. All rights reserved.