TY  - GEN
A1  - Pêcher, Arnaud
A1  - Wagler, Annegret
T1  - A construction for non-rank facets of stable set polytopes of webs
N2  - Graphs with circular symmetry, called webs, are relevant for describing the stable set polytopes of two larger graph classes, quasi-line graphs [{\sl Giles and Trotter 1981, Oriolo 2001}] and claw-free graphs [{\sl Galluccio and Sassano 1997, Giles and Trotter 1981}]. Providing a decent linear description of the stable set polytopes of claw-free graphs is a long-standing problem [{\sl Grötschel, Lov\'asz, and Schrijver 1988}]. However, even the problem of finding all facets of stable set polytopes of webs is open. So far, it is only known that stable set polytopes of webs with clique number $\leq 3$ have rank facets only [{\sl Dahl 1999, Trotter 1975}] while there are examples with clique number $\geq 4$ having non-rank facets [{\sl e.g. Liebling et al. 2003, Oriolo 2001, P\^echer and Wagler 2003}]. In this paper, we provide a construction for non-rank facets of stable set polytopes of webs. We use this construction to prove, for several fixed values of $\omega$ including all odd values at least 5, that there are only finitely many webs with clique number $\omega$ whose stable set polytopes admit rank facets only.
T3  - ZIB-Report - 03-21 
KW  - web
KW  - rank-perfect graph
KW  - stable set polytope
KW  - (non-)rank facet
Y1  - 2003
UR  - https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/743
UR  - https://nbn-resolving.org/urn:nbn:de:0297-zib-7437
ER  -