Even pairs in claw-free perfect graphs (Q1127877): Difference between revisions

An even pair in a graph is a pair of non-adjacent vertices such that every chordless path between them has even length. A graph is called strict quasi-parity when every induced subgraph that is not a clique has an even pair, and it is called perfectly contractile when every induced subgraph can be turned into a clique through a sequence of even-pair contractions. In this paper we determine the claw-free graphs that are strict quasi-parity and those that are perfectly contractile. We show that for both classes the minimal forbidden configurations are odd holes, antiholes and some line graphs of bipartite graphs, as conjectured by several authors. Our proofs are constructive and yield polynomial-time algorithms for the recognition of both classes.