
Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations w.r.t different concepts. Perfect graphs are, e.g., characterized as precisely those graphs G where the stable set polytope STAB(G) coincides with the clique constraint stable set polytope QSTAB(G). For all imperfect graphs STAB(G) ⊂ QSTAB(G) holds and, therefore, it is natural to measure imperfection in terms of the difference between STAB(G) and QSTAB(G). Several concepts have been developed in this direction, for instance the dilation ratio of STAB(G) and QSTAB(G) which is equivalent to the imperfection ratio imp(G )o fG .T o determine imp(G), both knowledge on the facets of STAB(G) and the extreme points of QSTAB(G) is required. For that, we extend a well-known result on antiblocking polyhedra by establishing a 1-1 correspondence between extreme points of QSTAB(G) and facet-defining subgraphs of G. We discuss several consequences, in particular, we give alternative proofs of several well-known results.
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
