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

AbstractThe SUM COLORING problem consists of assigning a color c(vi)∈Z+ to each vertex vi∈V of a graph G=(V,E) so that adjacent nodes have different colors and the sum of the c(vi)'s over all vertices vi∈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;2χ(G)−1}. Examples from the papers [Discrete Math. 174 (1999) 125; Algorithmica 23 (1999) 109] show that the bound is tight