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.
Sum coloring and interval graphs: a tight upper bound for the minimum number of colors
NICOLOSO Sara
2004
Abstract
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.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
