A New and Fast Evolutionary Algorithm for Strict Strong Graph Coloring Problem

This paper tackles the strict strong graph coloring (SSColoring). This graph coloring task aims at finding the minimum number of colors where each vertex dominates at least one non-empty color class. This problem has been solved for trees and proved to be NP-complete for general graphs. The present work introduces a new evolutionary algorithm for solving the SSColoring problem for general graphs. Contrary to the evolutionary algorithm proposed in [1], the proposed variant searches an optimal SSColoring using legal coloring space, a particular crossover and a polynomial optimization operator. Through experiments, we show that the proposed approach gives better results than previous approaches.