Séminaire Lotharingien de Combinatoire, B33e (1994)
A survey of the strong perfect graph conjecture and some recent results
The Strong Perfect Graph Conjecture (SPGC) claims that a graph
G is perfect if and only if none of its induced subgraphs
is an odd hole or an odd antihole. There are several classes of
graphs which are known to be perfect, and some graph transformations
which lead from known perfect graphs to new ones; in both cases SPGC is obviously
true. For many classes of graphs SPGC is already proved.
A possible counterexample, escpecially a minimally imperfect graph.
must fulfill a great lot of conditions; part of these conditions are
structural properties, the other ones can be expressed in terms of
graph invariants. It is shown here that SPGC is valid for
all graphs with a genus
less than or equal to 5, and that some classes of values for the number of
vertices in a counterexample can be excluded.
Institut f. Wirtschafts- u. Rechtswissenschaften
der TU München
The Tex, dvi, ps files of the paper will soon be available.