Polyhedral results for the equitable coloring problem

DOI10.1016/J.ENDM.2011.05.028MaRDI QIDQ2840701zbMATH OpenOpenAlexFDO

Authors Isabel Méndez-Díaz, D. Severín, G. Nasini

Publication date 23 July 2013

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1106.3349

zbMATH Keywords

branch \& cutequitable graph coloringinteger programming

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Combinatorial optimization (90C27)

Abstract: 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 of the effectiveness of including these inequalities as cuts in a Branch & Cut algorithm.

Recommendations

• A polyhedral approach for the equitable coloring problem
• A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives
• Equitable coloring of some convex polytope graphs
• A polyhedral approach for graph coloring
• A DSATUR-based algorithm for the equitable coloring problem

Cites work

• A branch-and-cut algorithm for equitable coloring based on a formulation by representatives
• A cutting plane algorithm for graph coloring
• Equitable Coloring
• Graph Colorings
• On the asymmetric representatives formulation for the vertex coloring problem

Cited in

(5)

• Equitable coloring of some convex polytope graphs
• Facets of the graph coloring polytope
• A polyhedral approach for the equitable coloring problem
• A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives
• scientific article; zbMATH DE number 7058467 (Why is no real title available?)

This page was built for publication: Polyhedral results for the equitable coloring problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2840701)