Following Bland, Huang, and Trotter [ MR 80g:05034];[ MR 86e:05075] a graph is called partitionable if, for some and , it has vertices and, no matter which vertex is removed, the set of the remaining vertices can be partitioned into pairwise disjoint cliques of size and also into pairwise disjoint stable sets of size . Odd holes and odd antiholes are partitionable; many additional partitionable graphs have been constructed by V. Chvátal, R. L. Graham, A. F. Perold, and S. H. Whitesides [ MR 81b:05044].
A small transversal in a graph is a set of vertices which meets all cliques of size and all stable sets of size . The following problem is an easier variation on a conjecture contributed to the 1993 [workshop on perfect graphs] by Gurvich and Temkin and on two conjectures proposed by Bacso, Boros, Gurvich, Maffray, and Preissmann [ MR 2000h:05116].
Conjecture. Every partitionable graph with and has a small transversal or else contains a hole of length five.
One of the milestones in the development of our understanding of perfect graphs was the theorem of Lovasz [46 #8885], asserting that every minimal imperfect graph has precisely +1 vertices. This theorem implies that every minimal imperfect graph is partitionable and that - as pointed out by Chvatal [ MR 86h:05091] - no minimal imperfect graph contains a small transversal. It follows that a proof of the conjecture would provide another proof of the Strong Perfect Graph Theorem.
A partitionable graph without a small transversal has been constructed by by Chvatal, Graham, Perold, and Whitesides (op.cit.). Its vertices are ; vertices and are adjacent if and only if is one of .
Ara Markosian claims [here] that this is the only known partitionable graph without a small transversal. One of the many holes of length five in this graph is
Additional information on related results and problems can be found [here]
Contributed by Vasek Chvatal
Back to the main index for Perfect Graphs.