Minimum sum coloring problem: Upper bounds for the chromatic strength

The minimum sum coloring problem (MSCP) is a vertex coloring problem in which a weight is associated with each color. Its aim is to find a coloring of the vertices of a graph G with the minimum sum of the weights of the used colors. The MSCP has important applications in the fields such as scheduling and VLSI design. The minimum number of colors among all optimal solutions of the MSCP for G is called the chromatic strength of G and is denoted by s(G). A tight upper bound of s(G) allows to significantly reduce the search space when solving the MSCP. In this paper, we propose and empirically evaluate two new upper bounds of s(G) for general graphs, UBA and UBS, based on an abstraction of all possible colorings of G formulated as an ordered set of decreasing positive integer sequences. The experimental results on the standard benchmarks DIMACS and COLOR show that UBA is competitive, and that UBS is significantly tighter than those previously proposed in the literature for 70 graphs out of 74 and, in particular, reaches optimality for 8 graphs. Moreover, both UBA and UBS can be applied to the more general optimum cost chromatic partition (OCCP) problem.