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.
