Lifted, projected and subgraph-induced inequalities for the representatives kk-fold coloring polytope

A kk-fold xx-coloring of a graph GG is an assignment of (at least) kk distinct colors from the set {1,2,…,x}{1,2,…,x} to each vertex such that any two adjacent vertices are assigned disjoint sets of colors. The kkth chromatic number of  GG, denoted by  χk(G)χk(G), is the smallest xx such that GG admits a kk-fold xx-coloring. We present an integer linear programming formulation (ILP) to determine χk(G)χk(G) and study the facial structure of the corresponding polytope Pk(G)Pk(G). We show facets that  Pk+1(G)Pk+1(G) inherits from Pk(G)Pk(G) and show how to lift facets from Pk(G)Pk(G) to Pk+ℓ(G)Pk+ℓ(G). We project facets of P1(G∘Kk)P1(G∘Kk) into facets of Pk(G)Pk(G), where G∘KkG∘Kk is the lexicographic product of GG by a clique with kk vertices. In both cases, we can obtain facet-defining inequalities from many of those known for the 11-fold coloring polytope. We also derive facets of Pk(G)Pk(G) from facets of stable set polytopes of subgraphs of GG. In addition, we present classes of facet-defining inequalities based on strongly χkχk-critical webs and antiwebs, which extend and generalize known results for 11-fold coloring. We introduce this criticality concept and characterize the webs and antiwebs having such a property.