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 - 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 -