An exact algorithm for the minimum sum coloring problem on partially decomposable graphs

Given an undirected graph G, the Minimum Sum Coloring Problem (MSCP) asks to find a legal vertex coloring of G using natural numbers that minimizes the total sum of the colors. In this paper, we propose an exact approach for MSCP using the modular decomposition tree of G, where our optimal solution is obtained at the root by the end of the process. This approach, called Modular Decomposition for Sum Coloring (MDSC), arises from the observation that decomposing graph G into disjoint subgraphs requires a careful selection of at least one solution from each subgraph, contributing to the final optimal solution. The modular decomposition technique aids us in making these selections intelligently. As a result, the branch and bound process becomes more efficient, faster, and powerful for solving MSCP on partially decomposable graphs. Numerical experiments demonstrate this improvement on several large DIMACS, COLOR 2002–2004 challenge graphs, and our generated instances, each containing between 500 and 1500 vertices.