The SUM COLORING problem consists of assigning a color c(v_i)∈Z~+ to each vertex viV 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∈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_x(G)-1}. Examples from the papers [Discrete Math. 174 (1999) 125; Algorithmica 23 (1999) 109] show that the bound is tight.
展开▼
