### G-2011-75

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

## Claudia Archetti, Nicola Bianchessi, and Alain Hertz

Given a graph *G*, an integer *k*, and a cost *c _{uv}* 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.

Published **December 2011**
,
18 pages

This cahier was revised in **December 2012**