Recursive generation of partitionable graphs

E. Boros, V. Gurvich, S. Hougardy

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


Results of Lovász (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átal, Graham, Perold, and Whitesides (1979). Results of Sebö (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 (and we conjecture that the same will hold for bigger α, too) and many but not all for (ω, α) = (4,4) and (4,5). Here, α and ω are respectively the clique and stability numbers of a partitionable graph, that is the numbers of vertices in its maximum cliques and stable sets. 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 are no counterexamples to Berge's conjecture (cf. Sebö (1996)), however this question is still open.

Original languageEnglish (US)
Pages (from-to)259-285
Number of pages27
JournalJournal of Graph Theory
Issue number4
StatePublished - Dec 2002

All Science Journal Classification (ASJC) codes

  • Geometry and Topology


  • Critical clique
  • Critical edge
  • Partitionable graph
  • Perfect graph


Dive into the research topics of 'Recursive generation of partitionable graphs'. Together they form a unique fingerprint.

Cite this