Partitionable graphs and odd holes

Let $G=(V,E)$ be a graph, and $\alpha,\omega$ arbitrary natural numbers. Assume that $a,v,b\in V, av\in E, vb\notin E$ are such that $G-a$, $G-v$ have a partition of size $\alpha$ into $\omega$-cliques, and $G-v$, $G-b$ have a partition of size $\omega$ into $\alpha$-stable sets. It is easy to show then that $G$ 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.