@misc{Wagler, author = {Wagler, Annegret}, title = {Critical and Anticritical Edges in Perfect Graphs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6174}, number = {00-49}, abstract = {We call an edge \$e\$ of a perfect graph \$G\$ critical if \$G-e\$ is imperfect and say further that \$e\$ is anticritical with respect to the complementary graph \$\overline G\$. We ask in which perfect graphs critical and anticritical edges occur and how to find critical and anticritical edges in perfect graphs. Finally, we study whether we can order the edges of certain perfect graphs such that deleting all the edges yields a sequence of perfect graphs ending up with a stable set.}, language = {en} } @misc{Wagler, author = {Wagler, Annegret}, title = {Antiwebs are Rank-Perfect}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6742}, number = {02-07}, abstract = {\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.}, language = {en} } @misc{HougardyWagler, author = {Hougardy, Stefan and Wagler, Annegret}, title = {Perfectness is an Elusive Graph Property}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6787}, number = {02-11}, abstract = {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.}, language = {en} } @misc{Wagler, author = {Wagler, Annegret}, title = {Rank-Perfect and Weakly Rank-Perfect Graphs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6448}, number = {01-18}, abstract = {An edge of a perfect graph \$G\$ is critical if \$G-e\$ is imperfect. We would like to decide whether \$G - e\$ is still {\sl almost perfect} or already {\sl very imperfect}. Via relaxations of the stable set polytope of a graph, we define two superclasses of perfect graphs: rank-perfect and weakly rank-perfect graphs. Membership in those two classes indicates how far an imperfect graph is away from being perfect. We study the cases, when a critical edge is removed from the line graph of a bipartite graph or from the complement of such a graph.}, language = {en} } @misc{Wagler, author = {Wagler, Annegret}, title = {The Classes of Critically and Anticritically Perfect Graphs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5975}, number = {00-29}, abstract = {We focus on two new types of extremal graphs with respect to perfectness: critically and anticritically perfect graphs that lose their perfectness by simply deleting and adding an arbitrary edge, respectively. We present examples and study properties in order to compare critically and anticritically perfect graphs with minimally imperfect graphs, another type of extremal graphs with respect to perfectness. We discuss two attempts to characterize the classes of all critically and anticritically perfect graphs and give a brief overview on classes of perfect graphs which contain critically or anticritically perfect graphs.}, language = {en} } @misc{Wagler, author = {Wagler, Annegret}, title = {Relaxing Perfectness: Which Graphs are 'Almost' Perfect?}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6700}, number = {02-03}, abstract = {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?}, language = {en} } @misc{PecherWagler, author = {Pecher, Arnaud and Wagler, Annegret}, title = {On Non-Rank Facets of Stable Set Polytopes of Webs with Clique Number Four}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7238}, number = {03-01}, abstract = {Graphs with circular symmetry, called webs, are relevant w.r.t. describing the stable set polytopes of two larger graph classes, quasi-line graphs and claw-free graphs. Providing a decent linear description of the stable set polytopes of claw-free graphs is a long-standing problem. However, even the problem of finding all facets of stable set polytopes of webs is open. So far, it is only known that stable set polytopes of webs with clique number \$\leq 3\$ have rank facets only while there are examples with clique number \$>4\$ having non-rank facets.}, language = {en} } @misc{PecherWagler, author = {P{\^e}cher, Arnaud and Wagler, Annegret}, title = {A construction for non-rank facets of stable set polytopes of webs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7437}, number = {03-21}, abstract = {Graphs with circular symmetry, called webs, are relevant for describing the stable set polytopes of two larger graph classes, quasi-line graphs [{\sl Giles and Trotter 1981, Oriolo 2001}] and claw-free graphs [{\sl Galluccio and Sassano 1997, Giles and Trotter 1981}]. Providing a decent linear description of the stable set polytopes of claw-free graphs is a long-standing problem [{\sl Gr{\"o}tschel, Lov\'asz, and Schrijver 1988}]. However, even the problem of finding all facets of stable set polytopes of webs is open. So far, it is only known that stable set polytopes of webs with clique number \$\leq 3\$ have rank facets only [{\sl Dahl 1999, Trotter 1975}] while there are examples with clique number \$\geq 4\$ having non-rank facets [{\sl e.g. Liebling et al. 2003, Oriolo 2001, P\^echer and Wagler 2003}]. In this paper, we provide a construction for non-rank facets of stable set polytopes of webs. We use this construction to prove, for several fixed values of \$\omega\$ including all odd values at least 5, that there are only finitely many webs with clique number \$\omega\$ whose stable set polytopes admit rank facets only.}, language = {en} } @misc{Wagler, author = {Wagler, Annegret}, title = {Critical and Anticritical Edges with respect to Perfectness}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7446}, number = {03-22}, abstract = {We call an edge \$e\$ of a perfect graph \$G\$ critical if \$G-e\$ is imperfect and call \$e\$ anticritical if \$G+e\$ is imperfect. The present paper surveys several questions in this context. We ask in which perfect graphs critical and anticritical edges occur and how to detect such edges. The main result by [{\sl Wagler, PhD thesis 2000}] shows that a graph does not admit any critical edge if and only if it is Meyniel. The goal is to order the edges resp.~non-edges of certain perfect graphs s.t. deleting resp.~adding all edges in this order yields a sequence of perfect graphs only. Results of [{\sl Hayward 1985}] and [{\sl Spinrad \& Sritharan 1995}] show the existence of such edge orders for weakly triangulated graphs; the line-perfect graphs are precisely these graphs where all edge orders are perfect [{\sl Wagler 2001}]. Such edge orders cannot exist for every subclass of perfect graphs that contains critically resp.~anticritically perfect graphs where deleting resp.~adding an arbitrary edge yields an imperfect graph. We present several examples and properties of such graphs, discuss constructions and characterizations from [{\sl Wagler 1999, Wagler PhD thesis 2000}]. An application of the concept of critically and anticritically perfect graphs is a result due to [{\sl Hougardy \& Wagler 2002}] showing that perfectness is an elusive graph property.}, language = {en} } @misc{Wagler, author = {Wagler, Annegret}, title = {The Normal Graph Conjecture is true for Circulants}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7813}, number = {04-06}, abstract = {Normal graphs are defined in terms of cross-intersecting set families: a graph is normal if it admits a clique cover \$\cal Q\$ and a stable set cover \$\cal S\$ s.t.~every clique in \$\cal Q\$ intersects every stable set in \$\cal S\$. Normal graphs can be considered as closure of perfect graphs by means of co-normal products (K{\"o}rner 1973) and graph entropy (Czisz\'ar et al. 1990). Perfect graphs have been recently characterized as those graphs without odd holes and odd antiholes as induced subgraphs (Strong Perfect Graph Theorem, Chudnovsky et al. 2002). K{\"o}rner and de Simone observed that \$C_5\$, \$C_7\$, and \$\overline C_7\$ are minimal not normal and conjectured, as generalization of the Strong Perfect Graph Theorem, that every \$C_5\$, \$C_7\$, \$\overline C_7\$- free graph is normal (Normal Graph Conjecture, K{\"o}rner and de Simone 1999). We prove this conjecture for a first class of graphs that generalize both odd holes and odd antiholes, the circulants, by characterizing all the normal circulants.}, language = {en} }