Séminaire Lotharingien de Combinatoire, B33e (1994)

Dieter Gernert

A survey of the strong perfect graph conjecture and some recent results

Abstract. 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.

Dieter Gernert
Institut f. Wirtschafts- u. Rechtswissenschaften
der TU München
Arcisstr. 21
80333 München
Germany

The Tex, dvi, ps files of the paper will soon be available.