New Results on Minimal Strongly Imperfect Graphs

The characterization of strongly perfect graphs by a restricted list of forbidden induced subgraphs has remained an open question for a long time. The minimal strongly imperfect graphs which are simultaneous imperfect are only odd holes and odd antiholes (E. Olaru, 1996), but the entire list is not known, in spite of a lot of particular results in this direction. In this paper we give some new properties of the minimal strongly imperfect graphs. Thus we introduce the notion of critical (co-critical) pair of vertices, and we prove that any vertex of a minimal s-imperfect (minimal c-imperfect) graph is contained in a critical (co-critical) pair, and, in a minimal s-imperfect graph different from a cycle of length at least 5, any vertex is the center of a star cutset, or, if not, it belongs to a house or a domino. Also, we characterize the triangle-free minimal s-imperfect graphs. (By s-perfect we mean the complement of a strongly perfect graph.)