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.