TY - GEN A1 - Wagler, Annegret T1 - Relaxing Perfectness: Which Graphs are 'Almost' Perfect? N2 - For all perfect graphs, the stable set polytope STAB$(G)$ coincides with the fractional stable set polytope QSTAB$(G)$, whereas STAB$(G) \subset$ QSTAB$(G)$ holds iff $G$ is imperfect. Padberg asked in the early seventies 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? T3 - ZIB-Report - 02-03 KW - perfect graph KW - stable set polytope KW - relaxations Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6700 ER - TY - GEN A1 - Wagler, Annegret T1 - Antiwebs are Rank-Perfect N2 - \We discuss a nested collection of three superclasses of perfect graphs: near-perfect, rank-perfect, and weakly rank-perfect graphs. For that, we start with the description of the stable set polytope for perfect graphs and allow stepwise more general facets for the stable set polytopes of the graphs in each superclass. Membership in those three classes indicates how far a graph is away from being perfect. We investigate for webs and antiwebs to which of the three classes they belong. We provide a complete description of the facets of the stable set polytope for antiwebs (with help of a result due to Shepherd on near-bipartite graphs). The main result is that antiwebs are rankperfect. T3 - ZIB-Report - 02-07 KW - relaxations of perfect graphs KW - antiwebs KW - stable set polytope Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6742 ER - TY - GEN A1 - Hougardy, Stefan A1 - Wagler, Annegret T1 - Perfectness is an Elusive Graph Property N2 - A graph property is called elusive (or evasive) if every algorithm for testing this property has to read in the worst case $n\choose 2$ entries of the adjacency matrix of the given graph. Several graph properties have been shown to be elusive, e.g. planarity (Best et al) or $k$-colorability (Bollobas). A famous conjecture of Karp says that every non-trivial monotone graph property is elusive. We prove that a non-monotone but hereditary graph property is elusive: perfectness. T3 - ZIB-Report - 02-11 KW - perfect graph KW - elusive graph property Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6787 ER -