Generalized clique family inequalities for claw-free graphs

Providing a complete description of the stable set polytopes of claw-free graphs is a long-standing open problem [M. Grötschel, L. Lovász, A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, 1988]. For the subclass of quasi-line graphs, Ben Rebea conjectured and Eisenbrandt et al. [F. Eisenbrand, G. Oriolo, G. Stauffer, P. Ventura, Circular Ones Matrices and the Stable Set Polytope of Quasi-Line Graphs, in: Lecture Notes in Computer Science, 3509, 2005, pp. 291–305] recently proved that all non-trivial facets belong to only one class, the so-called clique family inequalities. For general claw-free graphs, however, more complex facets are required to describe the stable set polytope. We introduce a generalization of clique family inequalities, and prove that several facet-defining inequalities for general claw-free graphs are of this type.