Polyhedral studies of vertex coloring problems: the standard formulation

DOI10.1016/j.disopt.2016.05.001zbMath1387.05086OpenAlexW2414807664MaRDI QIDQ1751160

Javier Marenco, Diego Delle Donne

Publication date: 24 May 2018

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2016.05.001

zbMATH Keywords

vertex coloringpolyhedral characterizationstandard formulation

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A branch-and-cut algorithm for the minimum-adjacency vertex coloring problem
• A supernodal formulation of vertex colouring with applications in course timetabling
• The strong perfect graph theorem
• Cliques, holes and the vertex coloring polytope
• Distance-hereditary graphs
• Precoloring extension. I: Interval graphs
• Geometric algorithms and combinatorial optimization
• Frequency assignment in cellular phone networks
• On certain polytopes associated with graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Facets of the graph coloring polytope
• Algorithmic graph theory and perfect graphs
• A cutting plane algorithm for graph coloring
• A branch-and-cut algorithm for graph coloring
• A one-to-one correspondence between colorings and stable sets
• Graph colorings with local constraints -- a survey
• A Column Generation Approach for Graph Coloring
• Maximum matching and a polyhedron with 0,1-vertices
• On coloring problems with local constraints
• Exploring the complexity boundary between coloring and list-coloring

This page was built for publication: Polyhedral studies of vertex coloring problems: the standard formulation