The minimum chromatic violation problem: a polyhedral study

DOI10.1016/J.ENDM.2017.10.053MaRDI QIDQ2413191zbMATH OpenOpenAlexFDO

Authors Mónica Braga, D. Delle Donne, Javier Marenco, Maria E. Ugarte, M. C. Varaldo, Mariana S. Escalante

Publication date 9 April 2018

Full work available at URL https://doi.org/10.1016/j.endm.2017.10.053

zbMATH Keywords

chromatic violationinteger programmingvertex coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Integer programming (90C10)

Recommendations

• The minimum chromatic violation problem: a polyhedral approach
• Lifted, projected and subgraph-induced inequalities for the representatives \(k\)-fold coloring polytope
• Facets of the graph coloring polytope
• The convex recoloring problem: polyhedra, facets and computational experiments
• A polyhedral approach for graph coloring

Cites work

• A branch-and-cut algorithm for graph coloring
• A cutting plane algorithm for graph coloring
• Cliques, holes and the vertex coloring polytope
• Facets of the \(k\)-partition polytope
• On the asymmetric representatives formulation for the vertex coloring problem

Cited in

(3)

• Lifted, projected and subgraph-induced inequalities for the representatives \(k\)-fold coloring polytope
• A new approach on locally checkable problems
• The minimum chromatic violation problem: a polyhedral approach

This page was built for publication: The minimum chromatic violation problem: a polyhedral study

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