@article {IOPORT.05550531,
    author       = {Coulonges, Sylvain and P\^echer, Arnaud and Wagler, Annegret K.},
    title        = {Characterizing and bounding the imperfection ratio for some classes of graphs.},
    year         = {2009},
    journal      = {Mathematical Programming. Series A. Series B},
    volume       = {118},
    number       = {1 (A)},
    issn         = {0025-5610},
    pages        = {37-46},
    publisher    = {Springer-Verlag, Berlin},
    doi          = {10.1007/s10107-007-0182-9},
    abstract     = {Summary: Perfect graphs constitute a well-studied graph class with a rich structure, which is 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$) equals the fractional stable set polytope QSTAB($G$). The dilation ratio ${\text {min}}\{t : {\text {QSTAB}}(G) \subseteq t \,\,{\text {STAB}}(G)\}$ of the two polytopes yields the imperfection ratio of $G$. It is NP-hard to compute and, for most graph classes, it is even unknown whether it is bounded. For graphs $G$ such that all facets of STAB($G$) are rank constraints associated with antiwebs, we characterize the imperfection ratio and bound it by 3/2. Outgoing from this result, we characterize and bound the imperfection ratio for several graph classes, including near-bipartite graphs and their complements, namely quasi-line graphs, by means of induced antiwebs and webs, respectively.},
    identifier   = {05550531},
}