@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 = {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{Lukac, author = {Lukac, Sascha}, title = {Holes, Antiholes and Maximal Cliques in a Railway Model for a Single Track}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7939}, number = {04-18}, abstract = {We present a graph theoretical model for scheduling trains on a single unidirectional track between two stations. The set of departures of all possible train types at all possible (discrete) points of time is turned into an undirected graph \$\Gneu\$ by joining two nodes if the corresponding departures are in conflict. This graph \$\Gneu\$ has no odd antiholes and no \$k\$-holes for any integer \$k\geq 5\$. In particular, any finite, node induced subgraph of \$\Gneu\$ is perfect. For any integer \$r\geq 2\$ we construct minimal headways for \$r\$ train types so that the resulting graph \$\Gneu\$ has \$2r\$-antiholes and \$4\$-holes at the same time. Hence, \$\Gneu\$ is neither a chordal graph nor the complement of a chordal graph, in general. At the end we analyse the maximal cliques in \$G\$.}, 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} } @misc{KosterWagler, author = {Koster, Arie M.C.A. and Wagler, Annegret}, title = {The extreme points of QSTAB(G) and its implications}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9249}, number = {06-30}, abstract = {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) \subset\$ 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)\$ of \$G\$. To determine imp\$(G)\$, both knowledge on the facets of STAB\$(G)\$ and the extreme points of QSTAB\$(G)\$ is required. The anti-blocking theory of polyhedra yields all {\em dominating} extreme points of QSTAB\$(G)\$, provided a complete description of the facets of STAB\$(\overline G)\$ is known. As this is typically not the case, we extend the result on anti-blocking polyhedra to a {\em complete} characterization of the extreme points of QSTAB\$(G)\$ by establishing a 1-1 correspondence to the facet-defining subgraphs of \$\overline G\$. We discuss several consequences, in particular, we give alternative proofs of several famous results.}, language = {en} } @misc{KosterWagler, author = {Koster, Arie M.C.A. and Wagler, Annegret}, title = {Comparing Imperfection Ratio and Imperfection Index for Graph Classes}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8836}, number = {05-50}, abstract = {Perfect graphs constitute a well-studied graph class with a rich structure, 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)\$ coincides with the fractional stable set polytope \$QSTAB(G)\$. For all imperfect graphs \$G\$ it holds that \$STAB(G) \subset QSTAB(G)\$. It is, therefore, natural to use the difference between the two polytopes in order to decide how far an imperfect graph is away from being perfect; we discuss three different concepts, involving the facet set of \$STAB( G)\$, the disjunctive index of \$QSTAB(G)\$, and the dilation ratio of the two polytopes. Including only certain types of facets for \$STAB(G)\$, we obtain graphs that are in some sense close to perfect graphs, for example minimally immperfect graphs, and certain other classes of so-called rank-perfect graphs. The imperfection ratio has been introduced by (Gerke and McDiarmid, 2001) as the dilation ratio of \$STAB(G)\$ and \$QSTAB(G)\$, whereas (Aguilera et al., 2003) suggest to take the disjunctive index of \$Q STAB(G)\$ as the imperfection index of \$G\$. For both invariants there exist no general upper bounds, but there are bounds known for the imperfection ratio of several graph classes (Coulonges et al. 2005, Gerke and McDiarmid, 2001). Outgoing from a graph-theoretical interpretation of the imperfection index, we conclude that the imperfection index is NP-hard to compute and we prove that there exists no upper bound on the imperfect ion index for those graph classes with a known bounded imperfection ratio. Comparing the two invariants on those classes, it seems that the imperfection index measures imperfection much more roughly than the imperfection ratio; therefoe, discuss possible directions for refinements.}, language = {en} }