Published in Volume XVIII, 2008, pages 1-12

Authors: V. Anastasoaei and E. Olaru


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

Full Text (PDF)


  title={New Results on Minimal Strongly Imperfect Graphs},
  author={V. Anastasoaei and E. Olaru},
  journal={Scientific Annals of Computer Science},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  publisher={``A.I. Cuza'' University Press}