Academic Journals Database
Disseminating quality controlled scientific knowledge

New Results on Minimal Strongly Imperfect Graphs

Author(s): V. Anastasoaei | E. Olaru

Journal: Scientific Annals of Computer Science
ISSN 1843-8121

Volume: 18;
Start page: 1;
Date: 2008;
VIEW PDF   PDF DOWNLOAD PDF   Download PDF Original page

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

Robotic Process Automation Switzerland


Tango Rapperswil
Tango Rapperswil