A Recognition Algorithm for a Class of Partitionable Graphs that Satisfies the Normal Graph Conjecture

Mihai TĂLMACIU, Elena NECHITA, Gloria-Cerasela CRIŞAN
University of Bacău, Department of Mathematics and Informatics
8 Spiru Haret, Bacău, Romania

Abstract: A graph is normal if admits a clique cover and a stable set cover so that every clique may intersect every stable set. The Normal Graph Conjecture says that every {,,}-free graph is normal. In this paper we prove this conjecture for the class of O-graphs and we give a recognition algorithm for O-graphs.

Keywords: Normal graphs, O-graphs, Partitionable graphs, Partite graphs, Triangulated graphs.

Mihai Tălmaciu received his M.S. degree in Informatics from Alexandru Ioan Cuza University, Iaşi, Romania, in 1976 and the his Ph.D. degree in Information Sciences from the same institution in 2002. He is a Professor of the Mathematics and Informatics Department of the University of Bacău, Bacău, Romania. His areas of research include Combinatorics and Graphs Theory, Graph Algorithms and Numerical Analysis.

Elena Nechita received her M.S. degree in Informatics from Alexandru Ioan Cuza University, Iaşi, Romania, in 1987 and her Ph.D. degree in Information Sciences from the same institution in 2000. She is an Associate Professor of the Mathematics and Informatics Department of the University of Bacău, Bacău, Romania. Her areas of research include: Probability Theory, Artificial Intelligence and Evolutionary Computing.

Gloria-Cerasela Crişan received her M.S. degree in Informatics from University of Bucharest, Romania, in 1986 and the Ph.D. degree in Information Sciences from Alexandru Ioan Cuza University, Iaşi, in 2008. She is a Lecturer of the Mathematics and Informatics Department of the University of Bacău, Bacău, Romania. Her areas of research include Artificial Intelligence and Evolutionary Computing.

>>Full text
CITE THIS PAPER AS:
Mihai TĂLMACIU, Elena NECHITA, Gloria-Cerasela CRIŞAN, A Recognition Algorithm for a Class of Partitionable Graphs that Satisfies the Normal Graph Conjecture, Studies in Informatics and Control, ISSN 1220-1766, vol. 18 (4), pp. 349-354, 2009.