Complete multi-partite cutsets in minimal imperfect graphs (Q1322031)

We show that a minimal imperfect graph \(G\) cannot contain a cutset \(C\) which induces a complete multi-partite graph unless \(C\) is a stable set and \(G\) is an odd hole. This generalizes a result of Tucker, who proved that the only minimal imperfect graphs containing stable cutsets are the odd holes. It is also a special case of a conjecture of Chvátal.