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

Fatma TAMMAL

doi:10.1051/ro/2025140

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

2025-12-08

0

PRE

AI

DOI：10.1051/ro/2025140

Original

Original request for help

Save

Abstract

En 中文

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.

Keywords:

Minimum sum coloring

strength of graph

proper coloration

modular decomposition

exact method

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

Abstract

Journal

Organization