06-11
Results and conjectures on the stable set polytope of claw-free graphs
Preprint series: 06-11, Preprints
- MSC:
- 05C99 None of the above but in this section
Abstract: The question of a polyhedral description for claw-free graphs remains one of the interesting open problems in polyhedral combinatorics. Galluccio and Sassano characterized in 1997 the rank facets of claw-free graphs, but regarding their non-rank facets there was even no conjecture at hand so far. For the subclass of quasi-line graphs, Ben Rebea claimed 1980 and Eisenbrand et al. proved recently that all non-trivial facets of their stable set polytopes belong to only one class, the clique family inequalities. However, for claw-free but not quasi-line graphs clique family inequalities do not suffice: We show that the clique neighborhood constraints describing the stable set polytopes of graphs with stability number 2 (Cook 1987) are no clique family inequalities. Stauffer conjectured 2005 that certain clique neighborhood constraints are the only non-rank facets for claw-free but not quasi-line graphs with stability number at least 4. Further non-rank facets for the graphs with stability number 3 are presented by Giles & Trotter 1981 and Liebling et al. 2003 and, in fact, all the known difficult facets of claw-free graphs occur in this case. We exhibit that these facets are no clique family inequalities and show, as our main result, that all of them belong to only one class, the co-spanning 1-forest constraints. It turns out that clique neighborhood constraints are special co-spanning 1-forest constraints. Combining all those results enables us to formulate a conjecture on the non-rank facets for general claw-free graphs, stating that all of them are inequalities of two types only, namely either clique family inequalities (for quasi-line graphs) or co-spanning 1-forest constraints (for all other claw-free graphs).
Keywords: claw-free graphs, stable set polytope, non-rank facets
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.