@misc{KosterWagler2005, author = {Koster, Arie M.C.A. and Wagler, Annegret}, title = {Comparing Imperfection Ratio and Imperfection Index for Graph Classes}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8836}, number = {05-50}, year = {2005}, abstract = {Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations with respect to different concepts. Perfect graphs are, for instance, precisely those graphs \$G\$ where the stable set polytope \$STAB(G)\$ coincides with the fractional stable set polytope \$QSTAB(G)\$. For all imperfect graphs \$G\$ it holds that \$STAB(G) \subset QSTAB(G)\$. It is, therefore, natural to use the difference between the two polytopes in order to decide how far an imperfect graph is away from being perfect; we discuss three different concepts, involving the facet set of \$STAB( G)\$, the disjunctive index of \$QSTAB(G)\$, and the dilation ratio of the two polytopes. Including only certain types of facets for \$STAB(G)\$, we obtain graphs that are in some sense close to perfect graphs, for example minimally immperfect graphs, and certain other classes of so-called rank-perfect graphs. The imperfection ratio has been introduced by (Gerke and McDiarmid, 2001) as the dilation ratio of \$STAB(G)\$ and \$QSTAB(G)\$, whereas (Aguilera et al., 2003) suggest to take the disjunctive index of \$Q STAB(G)\$ as the imperfection index of \$G\$. For both invariants there exist no general upper bounds, but there are bounds known for the imperfection ratio of several graph classes (Coulonges et al. 2005, Gerke and McDiarmid, 2001). Outgoing from a graph-theoretical interpretation of the imperfection index, we conclude that the imperfection index is NP-hard to compute and we prove that there exists no upper bound on the imperfect ion index for those graph classes with a known bounded imperfection ratio. Comparing the two invariants on those classes, it seems that the imperfection index measures imperfection much more roughly than the imperfection ratio; therefoe, discuss possible directions for refinements.}, language = {en} } @misc{PecherWagler2003, author = {Pecher, Arnaud and Wagler, Annegret}, title = {On Non-Rank Facets of Stable Set Polytopes of Webs with Clique Number Four}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7238}, number = {03-01}, year = {2003}, abstract = {Graphs with circular symmetry, called webs, are relevant w.r.t. describing the stable set polytopes of two larger graph classes, quasi-line graphs and claw-free graphs. Providing a decent linear description of the stable set polytopes of claw-free graphs is a long-standing problem. 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 while there are examples with clique number \$>4\$ having non-rank facets.}, language = {en} } @misc{PecherWagler2003, author = {P{\^e}cher, Arnaud and Wagler, Annegret}, title = {A construction for non-rank facets of stable set polytopes of webs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7437}, number = {03-21}, year = {2003}, abstract = {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{\"o}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.}, language = {en} } @misc{Wagler2002, author = {Wagler, Annegret}, title = {Antiwebs are Rank-Perfect}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6742}, number = {02-07}, year = {2002}, abstract = {\We discuss a nested collection of three superclasses of perfect graphs: near-perfect, rank-perfect, and weakly rank-perfect graphs. For that, we start with the description of the stable set polytope for perfect graphs and allow stepwise more general facets for the stable set polytopes of the graphs in each superclass. Membership in those three classes indicates how far a graph is away from being perfect. We investigate for webs and antiwebs to which of the three classes they belong. We provide a complete description of the facets of the stable set polytope for antiwebs (with help of a result due to Shepherd on near-bipartite graphs). The main result is that antiwebs are rankperfect.}, language = {en} }