ON MINIMAL IMPERFECT GRAPHS WITH CIRCULAR SYMMETRY

Results of Lovasz and Padberg entail that the class of so-called parti tionable graphs contains all the potential counterexamples to Berge's famous Strong Perfect Graph Conjecture, which asserts that the only mi nimal imperfect graphs are the odd chordless cycles with at least five vertices (''odd holes'') and their complements (''odd antiholes''). O nly two constructions (due to Chvatal, Graham, Perold, and Whitesides) are known for making partitionable graphs. The first one does not pro duce any counterexample to Berge's Conjecture, as shown by Sebo. Here we prove that the second one does not produce any counterexample eithe r. This second construction is given by near-factorizations of cyclic groups based on the so-called ''British number systems'' introduced by De Bruijn. All the partitionable graphs generated by this second cons truction (in particular odd holes and odd antiholes) have circular sym metry. No other partitionable graph with circular symmetry is known, a nd we conjecture that none exists; in this direction we prove that any counterexample must contain a clique and a stable set with at least s ix vertices each. Also we prove that every minimal imperfect graph wit h circular symmetry must have an odd number of vertices. (C) 1998 John Wiley & Sons, Inc. J Graph Theory 29: 209-225, 1998.