Optimization Online


New facets and facet-generating procedures for the orientation model for vertex coloring problems

Diego Delle Donne(diegodd***at***gmail.com)
Javier Marenco(jmarenco***at***ungs.edu.ar)

Abstract: In this work, we study the \emph{orientation model} for vertex coloring problems with the aim of finding partial descriptions of the associated polytopes. We present new families of valid inequalities, most of them supported by paths of the input graph. We develop facet-generating procedures for the associated polytopes, which we denominate \emph{path-lifting procedures}. Given a path between two vertices and any two valid inequalities, the path-lifting procedure generates an infinite family of valid inequalities. We study conditions ensuring that the obtained inequalities define facets. Finally, we present a large family of valid inequalities, which is obtained by iteratively applying the path-lifting procedure. We conjecture that this family may be sufficient to completely describe the associated polytope when $G$ is a path.

Keywords: vertex coloring, orientation model, facet-generating procedures

Category 1: Combinatorial Optimization (Polyhedra )

Category 2: Integer Programming (Cutting Plane Approaches )

Citation: National University of General Sarmiento, Argentina and Université Paris 13, France. June, 2019.

Download: [PDF]

Entry Submitted: 07/02/2019
Entry Accepted: 07/02/2019
Entry Last Modified: 07/02/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society