A Metaheuristic Algorithm to Face the Graph Coloring Problem

Abstract

Let G=(V, E) be a graph with a vertex set V and set of edges E. The Graph Coloring Problem consists of splitting the set V into k independent sets (color classes); if two vertices are adjacent (i.e. vertices which share an edge), then they cannot have the same color. In order to address this problem, a plethora of techniques have been proposed in literature. Those techniques are especially based on heuristic algorithms, because the execution time noticeably increases if exact solutions are applied to graphs with more than 100 vertices. In this research, a metaheuristic approach that combines a deterministic algorithm and a heuristic algorithm is proposed, in order to approximate the chromatic number of a graph. This method was experimentally validated by using a collection of graphs from the literature in which the chromatic number is well-known. Obtained results show the feasibility of the metaheuristic proposal in terms of the chromatic number obtained. Moreover, when the proposed methodology is compared against robust techniques, this procedure increases the quality of the residual graph and improves the Tabu search that solves conflicts involved in a path as coloring phase.