97-58: On Minimally Imperfect Graphs with Circular Symmetry

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