Premium
Recursive generation of partitionable graphs
Author(s) -
Boros E.,
Gurvich V.,
Hougardy S.
Publication year - 2002
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10067
Subject(s) - combinatorics , mathematics , conjecture , counterexample , chordal graph , discrete mathematics , split graph , recursion (computer science) , indifference graph , block graph , graph , 1 planar graph , algorithm
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. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 259–285, 2002