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.
Citation
National University of General Sarmiento, Argentina and Université Paris 13, France. June, 2019.