Lifting theorems and facet characterization for a class of clique partitioning inequalities

In this paper we prove two lifting theorems for the clique partitioning polytope, which provide sufficient conditions for a valid inequality to be facet-defining. In particular, if a valid inequality defines a facet of the polytope corresponding to the complete graph Km on m vertices, it defines a facet for the polytope corresponding to Kn for all n>m. This answers a question raised by Grötschel and Wakabayashi. Further, for the case of arbitrary graphs, we characterize when the so-called 2-partition inequalities define facets.