Recognizing Even Pairs

Can one decide in polynomial time if a given Berge graph has an even pair? (The general problem, i.e., not restricted to Berge graphs, is known to be co-NP-complete.)

Contributed by Frédéric Maffray

Can one find even pairs using balanced skew-partitions? (Is there always an even pair in the cutset of a balanced skew-partition?)

Contributed by Bruce Ree




Back to the main index for Perfect Graphs.