  Given an undirected graph $G = (V,E)$ with a set $V$ of vertices and a set
$E$ of edges, the minimum sum coloring problem (MSCP) is to find a legal vertex
coloring of $G$, using colors represented by natural numbers $1, 2, . . .$ such
that the total sum of the colors assigned to the vertices is minimized. This
paper describes an approach based on the decomposition of the original graph
into disjoint cliques for computing lower bounds for the MSCP. Basically, the
proposed approach identifies and removes at each extraction iteration a maximum
number of cliques of the same size (the largest possible) from the graph.
Computational experiments show that this approach is able to improve on the
current best lower bounds for 14 benchmark instances, and to prove optimality
for the first time for 4 instances. We also report lower bounds for 24 more
instances for which no such bounds are available in the literature. These new
lower bounds are useful to estimate the quality of the upper bounds obtained
with various heuristic approaches.
