A polyhedral approach for the equitable coloring problem

DOI10.1016/j.dam.2012.11.018zbMath1288.05098OpenAlexW2125283791MaRDI QIDQ2448876

Daniel Severín, Isabel Méndez-Díaz, Graciela L. Nasini

Publication date: 5 May 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2012.11.018

zbMATH Keywords

integer programmingequitable graph coloringcut and branch

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Coloring of graphs and hypergraphs (05C15)

Related Items

Improving lower bounds for equitable chromatic number ⋮ A DSATUR-based algorithm for the equitable coloring problem ⋮ A Tabu Search Heuristic for the Equitable Coloring Problem ⋮ A polyhedral approach for the equitable coloring problem ⋮ A flow based pruning scheme for enumerative equitable coloring algorithms ⋮ Solving vertex coloring problems as maximum weight stable set problems

Cites Work

• A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives
• The maximum \(k\)-colorable subgraph problem and orbitopes
• Testing cut generators for mixed-integer linear programming
• Conflict-free star-access in parallel memory systems
• Packing and partitioning orbitopes
• The equitable colorings of Kneser graphs
• Equitable coloring of trees
• A polyhedral approach for the equitable coloring problem
• A cutting plane algorithm for graph coloring
• On the asymmetric representatives formulation for the vertex coloring problem
• A Branch-and-Cut Algorithm for Equitable Coloring based on a Formulation by Representatives
• A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
• Equitable Coloring
• Graph Colorings
• Perfect Graphs and an Application to Optimizing Municipal Services
• Unnamed Item

This page was built for publication: A polyhedral approach for the equitable coloring problem