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

Claudia Archetti*, Nicola Bianchessi, Alain Hertz

*Corresponding author for this work

    Research output: Contribution to JournalArticleAcademicpeer-review


    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.

    Original languageEnglish
    Pages (from-to)49-59
    Number of pages11
    JournalDiscrete Applied Mathematics
    Publication statusPublished - 11 Mar 2014


    • Branch-and-price algorithm
    • Graph coloring
    • Robust solution
    • Tabu search


    Dive into the research topics of 'A branch-and-price algorithm for the robust graph coloring problem'. Together they form a unique fingerprint.

    Cite this