Facet-inducing web and antiweb inequalities for the graph coloring polytope
For a graph G G and its complement G ? , we define the graph coloring polytope P(G) P ( G ) to be the convex hull of the incidence vectors of star partitions of G ? . We examine inequalities whose support graphs are webs and antiwebs appearing as induced subgraphs in G G . We show that for an antiweb W ? in G G the corresponding inequality is facet-inducing for P(G) P ( G ) if and only if W ? is critical with respect to vertex colorings. An analogous result is also proved for the web inequalities.
graph coloring polytopes polyhedral combinatorics