Recursive Generation of Partitionable Graphs

Results of Lovasz (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 Chvatal, Graham, Perold and Whitesides (1979). Results of Sebo (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 all the partitionable graphs with # = 3, # # 9 (we conjecture that the same will hold for bigger #, too) and 'almost all' for (#, #) = (4, 4) and (4, 5). Here # and # 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 critical #-clique, that is an #-clique which intersects only 2# - 2 other #-cliques. This property might imply that in our class there a..