  The Minimum Sum Coloring Problem is a variant of the Graph Vertex Coloring
Problem, for which each color has a weight. This paper presents a new way to
find a lower bound of this problem, based on a relaxation into an integer
partition problem with additional constraints. We improve the lower bound for
18 graphs of standard benchmark DIMACS, and prove the optimal value for 4
graphs by reaching their known upper bound.
