\input zb-basic
\input zb-ioport
\iteman{io-port 05550531}
\itemau{Coulonges, Sylvain; P\^echer, Arnaud; Wagler, Annegret K.}
\itemti{Characterizing and bounding the imperfection ratio for some classes of graphs.}
\itemso{Math. Program. 118, No. 1 (A), 37-46 (2009).}
\itemab
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.
\itemrv{~}
\itemcc{}
\itemut{}
\itemli{doi:10.1007/s10107-007-0182-9}
\end