An improved bi-criteria evolutionary approach for the sum coloring of graphs

¹ Higher Institute of Management and Computer Science ISIGK, Kairouan University, Kairouan, Tunisia
² Institute of Advanced Business Studies of Carthage, Carthage University, IHEC Carthage Presidency-2017, Tunis, Tunisia
³ LARODEC laboratory, Higher School of Economic and Commercial Sciences of Tunis, Tunis University, Abou Zakaria Al Hafsi Street, Tunis, Tunisia

^* Corresponding author: olfaharrabikhlif@gmail.com

Received: 28 March 2025
Accepted: 15 October 2025

Abstract

The sum coloring problem emerged as an interesting variant of the classical graph coloring problem since it is able to model several life applications. Interestingly, the studied problem could perform a straightforward implementation of many important complex problems such as timetabling, scheduling and resource allocation. In this work, we propose an original bi-criteria optimization method that tries to separately consider two objective functions when solving the sum coloring problem. The computational performance of our approach, based on a set of benchmark instances, shows a significant improvement of the chromatic sum bounds.