A New Ant Colony Optimization Algorithm for the Lower Bound of Sum Coloring Problem

We consider an undirected graph G =(V, E), the minimum sum coloring problem (MSCP) asks to find a valid vertex coloring of G, using natural numbers (1,2,…), the aim is to minimize the total sum of colors. In this paper we are interested in the elaboration of an approximate solution for the minimum sum coloring problem (MSCP), more exactly we try to give a lower bound for MSCP by looking for a decomposition of the graph based on the metaheuristic of ant colony optimization (ACO). We test different instances to validate our approach.