Rank-Perfect and Weakly Rank-Perfect Graphs

Please always quote using this URN: urn:nbn:de:0297-zib-6448
  • 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Annegret Wagler
Document Type:ZIB-Report
Tag:critical edges; perfect graphs; rank-perfect graphs; stable set polytope; weakly rank-perfect graphs
MSC-Classification:05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15)
Date of first Publication:2001/08/03
Series (Serial Number):ZIB-Report (01-18)
Published in:Appeared in: Math. Meth. of Oper. Res. 95 (2002) 127-149