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(v_i ) \in Z_+$ to each vertex $v_i \in V$ of a graph $G = (V; E)$ so that adjacent nodes have different colors and the sum of the $c(v_i )$'s over all vertices $v_i \in 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\chi(G) - 1\}$. Examples from the papers [Discrete Math. 174 (1999) 125; Algorithmica 23 (1999) 109] show that the bound is tight.