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

¹ LaROMaD, Fac. Maths, USTHB, PB 32 Bab Ezzouar, 16111 Algiers, Algeria
² EPROAD EA 4669, UPJV, 7 rue du Moulin Neuf, 80000 Amiens, France

^* Corresponding author: This email address is being protected from spambots. You need JavaScript enabled to view it.

Received: 4 November 2024
Accepted: 13 October 2025

Abstract

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.