Regresar

New framework for conflict-free coloring of hypergraphs and other graph coloring problems

Abstract:

A new framework for conflict-free coloring of hypergraphs is presented, leading to a novel graph problem which generalizes the partition and the list coloring problems, well-known for their multiple applications. Two integer linear programming formulations are proposed for this problem: a compact formulation inspired by the pioneering formulation for the vertex coloring problem and a set covering formulation whose variables are associated with stable sets. For the latter formulation, a branch-and-price algorithm is developed. Computational experiments in random instances validate the superiority of this approach over the direct solution of the compact formulation with a commercial solver.