DIMACS TR: 99-31

Recursive Generation of Partitionable Graphs

Authors: E.Boros, V.Gurvich and S.Hougardy


Results of Lov\'asz (1972) and Padberg (1974) imply that partitionable graphs contain all the potential counterexamples to Berge's famous Strong Perfect Graph Conjecture. A recursive method of generating partitionable graphs was suggested by Chv\'atal, Graham, Perold and Whitesides (1979). Results of Seb\H{o} (1996) entail that Berge's conjecture holds for all the partitionable graphs obtained by this method. Here we suggest a more general recursion. Computer experiments show that it generates {\em all} the partitionable graphs with $\go = 3, \ga \leq 9$ (we conjecture that the same will hold for bigger $\ga$, too) and 'almost all' for $(\go,\ga) = (4,4)$ and $(4,5)$. Here $\ga$ and $\go$ are respectively the clique and stability numbers of a partitionable graph, i.e. numbers of vertices in its maximum clique and stable set. All the partitionable graphs generated by our method contain a {\em critical $\go$-clique}, that is an $\go$-clique which intersects only $2\go-2$ other $\go$-cliques. This property might imply that in our class there are no counterexamples to Berge's conjecture (c.f. Seb\H{o} (1996)), however this question is still open.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1999/99-31.ps.gz
DIMACS Home Page