New Results on Minimal Strongly Imperfect Graphs

Published in Volume XVIII, 2008, pages 1-12

Authors: V. Anastasoaei and E. Olaru

Abstract

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)

References

[1] C. Berge, P. Douchet, Strongly perfect graphs, Annals of Discrete Mathematics, 21, pp. 57-61, 1984.

[2] F. Bonomo, M. Chudnovsky, G. Duran, Partial characterizations of clique-perfect graphs I: subclasses of claw-free graphs, Discrete Applied Mathematics, 156(7), pp. 1058-1082, 2008.

[3] M.Chudnovsky, G.Cornu´ejols, X. Liu, P. Seymour, K. Vuˇskovi´c, Recognizing Berge graphs, Combinatorica, 25, pp. 143-186, 2005.

[4] M. Chudnovsky, N. Robertson, P. Seymour, R. Thomas, The strong perfect graph theorem, Annals of Mathematics, 164, pp. 51-229, 2006.

[5] V. Chvatal, Perfectly orderable graphs, in: Topics on perfect graphs, Annals of Discrete Mathematics, 21, pp. 63-65, 1984.

[6] V.Chvatal, I.Rusu, A Note on Graphs Without Long Holes, 1st Workshop on perfect graphs, Princeton, New Jersey, U.S.A., 1993.

[7] S. Hougardy, Classes of perfect graphs, Discrete Mathematics, 306 (19- 20), pp. 2529-2571, 2006.

[8] B. Jamison, S. Olariu, On the semi-perfect elimination, Advances in Applied Mathematics, 9, pp. 364-376, 1988.

[9] E. Olaru, The structure of imperfect critically strongly-imperfect graphs, Discrete Mathematics, 156, pp. 299-302, 1996.

[10] E. Olaru, On strongly perfect graphs and the structure of criticallyimperfect graphs, Analele Stiintifice ale Universitatii ”Al.I.Cuza” Iasi, Tomul II, Informatica, pp. 45-59, 1993.

[11] E. Olaru, G. Alexe, On the graph structure of k-transitive symmetric relations, Studii si Cercetari Matematice (Mathematical Reports), Tomul 50, 5-6, pp. 395-407, 1998.

[12] G. Ravindra, Meyniel graphs are strongly perfect, Journal of Combinatorial Theory, Series B, 35(2), pp. 187-190, 1982.

[13] G. Ravindra, Some classes of strongly perfect graphs, Discrete Mathematics, 206, pp. 197-203, 1999.

Bibtex

@article{sacscuza:anastasoaei2008nromsig,
  title={New Results on Minimal Strongly Imperfect Graphs},
  author={V. Anastasoaei and E. Olaru},
  journal={Scientific Annals of Computer Science},
  volume={18},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  year={2008},
  pages={1--12},
  publisher={``A.I. Cuza'' University Press}
}