Characterizing and bounding the imperfection ratio for some classes of graphs.

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 $${\rm min}\{t : {\rm QSTAB}(G) \subseteq t\,{\rm 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. [ABSTRACT FROM AUTHOR]