Two lagrangian relaxation based heuristics for vertex coloring problem

Vertex coloring problem is a well-known NP-Hard problem where the objective is to minimize the number of colors used to color vertices of a graph ensuring that adjacent vertices cannot have same color. In this paper, we first discuss existing mathematical formulations of the problem and then consider two different heuristics, namely HEUR-RA and HEUR-RC, based on Lagrangian relaxation of adjacency and coloring constraints. HEUR-RA does not require solving any optimization problem through execution whereas at each iteration of HEUR-RC another NP-Hard problem, maximal weight stable set problem, is solved. We conduct experiments to observe computational performances of these heuristics. The experiments reveal that although it requires longer running times, HEUR-RC outperforms HEUR-RA since it provides lower optimal gaps as well as upper bound information.