A Branch-and-Price Approach for Graph Multi-Coloring

We present a branch-and-price framework for solving the graph multicoloring problem. We propose column generation to implicitly optimize the linear programming relaxation of an independent set formulation (where there is one variable for each independent set in the graph) for graph multi-coloring. This approach, while requiring the solution of a difficult subproblem, is a promising method to obtain good solutions for small to moderate size problems quickly. Some implementation details and initial computational experience are presented.