A branch-and-price algorithm for the robust graph coloring problem

Given a graph GG, an integer kk, and a cost cuvcuv associated with all pairs uvuv of non-adjacent vertices in GG, the robust graph coloring problem is to assign a color in {1,…,k}{1,…,k} to every vertex of GG so that no edge has both endpoints with the same color, and the total cost of the pairs of vertices having the same color is minimum. We propose a branch-and-price algorithm for the solution of this problem. The pricing problem consists in finding a stable set of minimum total weight, and we propose both an exact and a heuristic algorithm for its solution. Computational experiments are reported for randomly generated and benchmark graph coloring instances.