TY - GEN A1 - Wagler, Annegret T1 - Critical and Anticritical Edges in Perfect Graphs N2 - 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. T3 - ZIB-Report - 00-49 KW - perfect graphs KW - critical edges KW - anticritical edges Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6174 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 - TY - GEN A1 - Wagler, Annegret T1 - Rank-Perfect and Weakly Rank-Perfect Graphs N2 - 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. T3 - ZIB-Report - 01-18 KW - perfect graphs KW - rank-perfect graphs KW - weakly rank-perfect graphs KW - stable set polytope KW - critical edges Y1 - 2001 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6448 ER - TY - GEN A1 - Wagler, Annegret T1 - The Classes of Critically and Anticritically Perfect Graphs N2 - 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. T3 - ZIB-Report - 00-29 KW - perfect graphs KW - critically perfect graphs KW - anticritically perfect graphs Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5975 ER - 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 - Pecher, Arnaud A1 - Wagler, Annegret T1 - On Non-Rank Facets of Stable Set Polytopes of Webs with Clique Number Four N2 - 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. T3 - ZIB-Report - 03-01 KW - web KW - rank-perfect graph KW - stable set polytope KW - (non-)rank facet Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7238 ER - TY - GEN A1 - Pêcher, Arnaud A1 - Wagler, Annegret T1 - A construction for non-rank facets of stable set polytopes of webs N2 - 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ö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. T3 - ZIB-Report - 03-21 KW - web KW - rank-perfect graph KW - stable set polytope KW - (non-)rank facet Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7437 ER - TY - GEN A1 - Wagler, Annegret T1 - Critical and Anticritical Edges with respect to Perfectness N2 - 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. T3 - ZIB-Report - 03-22 KW - Perfect graphs KW - critical edges KW - perfect edge orders KW - critically perfect graphs Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7446 ER - TY - GEN A1 - Wagler, Annegret T1 - The Normal Graph Conjecture is true for Circulants N2 - 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ö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ö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ö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. T3 - ZIB-Report - 04-06 KW - perfect graphs KW - normal graphs KW - circulants Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7813 ER - TY - GEN A1 - Marenco, Javier A1 - Wagler, Annegret T1 - Chromatic Scheduling Polytopes coming from the Bandwidth Allocation Problem in Point-to-Multipoint Radio AccessSystems N2 - Point-to-Multipoint systems are one kind of radio systems supplying wireless access to voice/data communication networks. Such systems have to be run using a certain frequency spectrum, which typically causes capacity problems. Hence it is, on the one hand, necessary to reuse frequencies but, on the other hand, no interference must be caused thereby. This leads to the bandwidth allocation problem, a special case of so-called chromatic scheduling problems. Both problems are NP-hard, and there exist no polynomial time approximation algorithms with a guaranteed quality. One kind of algorithms which turned out to be successful for many other combinatorial optimization problems uses cutting plane methods. In order to apply such methods, knowledge on the associated polytopes is required. The present paper contributes to this issue, exploring basic properties of chromatic scheduling polytopes and several classes of facet-defining inequalities. T3 - ZIB-Report - 03-39 KW - Bandwidth allocation KW - polyhedral combinatorics Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7614 ER - TY - GEN A1 - Koster, Arie M.C.A. A1 - Wagler, Annegret T1 - The extreme points of QSTAB(G) and its implications N2 - 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. T3 - ZIB-Report - 06-30 KW - perfect graphs KW - imperfection ratio KW - stable set polytope Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9249 ER - TY - GEN A1 - Koster, Arie M.C.A. A1 - Wagler, Annegret T1 - Comparing Imperfection Ratio and Imperfection Index for Graph Classes N2 - 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. T3 - ZIB-Report - 05-50 KW - perfect graphs KW - imperfection ratio KW - imperfection index Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8836 ER - TY - THES A1 - Wagler, Annegret T1 - Critical Edges in Perfect Graphs Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10220 ER - TY - GEN A1 - Wagler, Annegret T1 - Critical Edges in Perfect Graphs and Some Polyhedral Consequences N2 - An edge $e$ of a perfect graph $G$ is called critical if $G-e$ is imperfect. For certain graphs $G-e$ of this type, we determine all minimally imperfect subgraphs. We use this knowledge to describe inequalities inducing facets of the stable set polytope associated with $G-e$.\\ T3 - ZIB-Report - SC-97-46 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3153 ER - TY - GEN A1 - Tuza, Zsolt A1 - Wagler, Annegret T1 - Minimally non-preperfect graphs of small maximum degree N2 - A graph $G$ is called preperfect if each induced subgraph $G' \subseteq G$ of order at least 2 has two vertices $x,y$ such that either all maximum cliques of $G'$ containing $x$ contain $y$, or all maximum indepentent sets of $G'$ containing $y$ contain $x$, too. Giving a partial answer to a problem of Hammer and Maffray [Combinatorica 13 (1993), 199-208], we describe new classes of minimally non-preperfect graphs, and prove the following characterizations: \begin{itemize} \item[(i)] A graph of maximum degree 4 is minimally non-preperfect if and only if it is an odd cycle of length at least 5, or the complement of a cycle of length 7, or the line graph of a 3-regular 3-connected bipartite graph. \item[(ii)] If a graph $G$ is not an odd cycle and has no isolated vertices, then its line graph is minimally non-preperfect if and only if $G$ is bipartite, 3-edge-connected, regular of degree $d$ for some $d \ge 3$, and contains no 3-edge-connected $d'$-regular subgraph for any $3 \le d' \le d$. \end{itemize} T3 - ZIB-Report - SC-97-28 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2971 ER - TY - GEN A1 - Wagler, Annegret T1 - On Critically Perfect Graphs N2 - A perfect graph is critical if the deletion of any edge results in an imperfect graph. We give examples of such graphs and prove some basic properties. We investigate the relationship of critically perfect graphs to well-known classes of perfect graphs and study operations preserving critical perfectness. T3 - ZIB-Report - SC-96-50 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2609 ER -