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 a clique 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.

Contributed by Frédéric Maffray

Back to the
main index
for Perfect Graphs.