Critical edges in perfect line graphs and some polyhedral consequences Original Research Article

An edge e of a perfect graph G is called critical if G−e is imperfect. Inequalities inducing facets of the stable set polytope associated with G−e are described in the case that G or G is the line graph of a bipartite graph. The proofs rely on a characterization of minimally imperfect subgraphs in G−e where G is a perfect line graph or its complement.