DIMACS TR: 99-31
Recursive Generation of Partitionable Graphs
Authors: E.Boros, V.Gurvich and S.Hougardy
ABSTRACT
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