## DIMACS TR: 97-58

## On Minimally Imperfect Graphs with Circular Symmetry

### Authors: Gábor Bacsó, Endre Boros, Vladimir Gurvich,
Frédéric Maffray and Myriam Preissmann

**
ABSTRACT
**

Results of Lovász and Padberg entail that the class of so-called
partitionable graphs contains all the potential counterexamples to
Berge's famous Strong Perfect Graph Conjecture (which asserts that the
only minimally imperfect graphs are the odd chordless cycles with at
least five vertices and their complements). Only two constructions
(due to Chvátal, Graham, Perold and Whitesides) are known for making
partitionable graphs. The first one does not produce any counterexample
to Berge's Conjecture, as shown by Sebö. Here we prove that the
second construction does not produce any counterexample either. We
conjecture that every partitionable graph with circular symmetry can be
generated by this second construction, and give results in this
direction. We also show that, regardless of this conjecture, every
minimally imperfect graph with circular symmetry must have an odd
number of vertices.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-58.ps.gz

DIMACS Home Page