Let be a graph, and arbitrary natural numbers. Assume that are such that , have a partition of size into -cliques, and , have a partition of size into -stable sets. It is easy to show then that is not perfect.

*Given the
four partitions, find an odd hole or an odd antihole. *

This would imply SPGC.

This contains the following:

*Given a partitionable graph (with all the partitions), find an odd hole or an odd antihole. Does the fact that the partitions are given make the task easier ? *

Contributed by András Sebo

Back to the
main index
for Perfect Graphs.