7. Relaxing Perfectness: Which Graphs Are “Almost” Perfect?
Annegret K. Wagler · Society for Industrial and Applied Mathematics eBooks · 2004
For all perfect graphs, the stable set polytope STAB(G) coincides with the fractional stable set polytope QSTAB(G), whereas STAB(G) ⊂ QSTAB(G) holds iff G is imperfect. In the early 1970s, Padberg asked for “almost” perfect graphs. He characterized those graphs for which the difference between STAB(G) and QSTAB(G) is smallest possible. We develop this idea further and define three polytopes between STAB(G) and QSTAB(G) by allowing certain sets of cutting planes only to cut off all the fractional vertices of QSTAB(G). The difference between QSTAB(G) and the largest of the three polytopes coinciding with STAB(G) gives some information on the stage of imperfectness of the graph G. We obtain a nested collection of three superclasses of perfect graphs and survey which graphs are known to belong to one of those three superclasses. This answers the question, Which graphs are “almost” perfect?