Complete multi-partite cutsets in minimal imperfect graphs (Q1322031)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Complete multi-partite cutsets in minimal imperfect graphs |
scientific article |
Statements
Complete multi-partite cutsets in minimal imperfect graphs (English)
0 references
5 May 1994
0 references
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.
0 references
minimal imperfect graph
0 references
cutset
0 references
complete multi-partite graph
0 references
stable set
0 references