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

Saved in:

Bibliographic Details
Title:	An exact algorithm for the minimum sum coloring problem on partially decomposable graphs.
Authors:	Tammal, Fatma¹ (AUTHOR) ftammal@usthb.dz, Aïder, Méziane^1,2 (AUTHOR)
Source:	RAIRO: Operations Research (2804-7303). 2025, Vol. 59 Issue 6, p3621-3648. 28p.
Subjects:	Graph coloring, Branch & bound algorithms, Deterministic algorithms, Graph theory, Mathematical optimization
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. [ABSTRACT FROM AUTHOR]
	Copyright of RAIRO: Operations Research (2804-7303) is the property of EDP Sciences and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database:	Engineering Source

Description
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. [ABSTRACT FROM AUTHOR]
ISSN:	28047303
DOI:	10.1051/ro/2025140