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.