A Branch-and-Price Algorithm for the Robust Graph Coloring Problem

, , and

BibTeX reference

Given a graph G, an integer k, and a cost cuv associated with all pairs uv of non-adjacent vertices in G, the robust graph coloring problem is to assign a color in {1,•,k} to every vertex of G 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.

, 18 pages

This cahier was revised in December 2012

Research Axis


, , and
Discrete Applied Mathematics, 165, 49–59, 2014 BibTeX reference