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

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