@misc{Wagler2001, 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}, year = {2001}, 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{Wagler2000, 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}, year = {2000}, 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} }