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
Additional Services
| 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) |
| ZIB-Reportnumber: | 01-18 |
| Published in: | Appeared in: Math. Meth. of Oper. Res. 95 (2002) 127-149 |
