A polyhedral approach for the equitable coloring problem

作者：Mendez Diaz Isabel^*; Nasini Graciela; Severin Daniel

来源：Discrete Applied Mathematics, 2014, 164: 413-426.

DOI：10.1016/j.dam.2012.11.018

• Equitable graph coloring
• Integer programming
• Cut and branch

In this work we study the polytope associated with a 0,1-integer programming formulation for the Equitable Coloring Problem. We find several families of valid inequalities and derive sufficient conditions in order to be facet-defining inequalities. We also present computational evidence that shows the efficacy of these inequalities used in a cutting-plane algorithm.

• 出版日期2014-2-19