The minimum chromatic violation problem: a polyhedral approach

DOI10.1016/J.DAM.2019.05.010MaRDI QIDQ2184668zbMATH OpenOpenAlexWikidataFDO

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

Publication date 29 May 2020

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

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

zbMATH Keywords

\(k\)-partitionchromatic violationgraph coloringpolyhedral study

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Polytopes and polyhedra (52B99) Integer programming (90C10) Programming involving graphs or networks (90C35)

Recommendations

• The minimum chromatic violation problem: a polyhedral study
• Lifted, projected and subgraph-induced inequalities for the representatives \(k\)-fold coloring polytope
• Facets of the graph coloring polytope
• Cliques, holes and the vertex coloring polytope
• A polyhedral approach for graph coloring

Cites work

• A branch-and-cut algorithm for graph coloring
• A branch-and-price algorithm for the (k,c)-coloring problem
• A cutting plane algorithm for graph coloring
• A graph coloring algorithm for large scheduling problems
• A supernodal formulation of vertex colouring with applications in course timetabling
• An exact approach for the vertex coloring problem
• An introduction to timetabling
• Cliques, holes and the vertex coloring polytope
• Compositions of Graphs and Polyhedra I: Balanced Induced Subgraphs and Acyclic Subgraphs
• Facets of the \(k\)-partition polytope
• Facets of the balanced (acyclic) induced subgraph polytope
• Facets of the Bipartite Subgraph Polytope
• Frequency assignment in cellular phone networks
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 1416629 (Why is no real title available?)
• On the asymmetric representatives formulation for the vertex coloring problem
• Polyhedral results for the bipartite induced subgraph problem
• The Maximum Induced Bipartite Subgraph Problem with Edge Weights
• Weakly bipartite graphs and the max-cut problem

Cited in

(3)

• Lifted, projected and subgraph-induced inequalities for the representatives \(k\)-fold coloring polytope
• The minimum chromatic violation problem: a polyhedral study
• On the complexity of the minimum chromatic violation problem

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

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