Rank-perfect and" weakly rank-perfect graphs |
| |
Authors: | Annegret K. Wagler |
| |
Affiliation: | (1) Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB), Takustr. 7, D-1195 Berlin, Germany (e-mail: wagler@zib.de), DE |
| |
Abstract: | An edge e of a perfect graph G is critical if G−e is imperfect. We would like to decide whether G−e is still “almost perfect” or already “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. |
| |
Keywords: | : perfect graph critical edge stable set polytope |
本文献已被 SpringerLink 等数据库收录! |
|