An even pair is a pair of vertices such that each chordless path between them has even length. Results of Fonlupt and Uhry, Meyniel, and also Bertschi and Reed imply that no minimal imperfect graph contains an even pair. A graph G is called quasi-parity (QP) if, for every induced subgraph H of G on at least two vertices, either H or its complement has an even pair. A graph G is called strict quasi-parity (SQP) if every induced subgraph H of G either H is aclique or has an even pair.
In the past 20 years many classical families of perfect graphs were proven to be SQP, which shows the interest of this class. However there are perfect graphs with no even pairs, e.g., all the line-graphs of 3-connected bipartite graphs.
None of the following questions or conjectures has been settled in full. Solutions are known only for special subclasses of graphs, e.g., planar graphs, claw-free graphs, bull-free graphs, etc.
Contributed by Frédéric Maffray
Back to the
main index
for Perfect Graphs.