VERIFICATION OF THE NORMAL GRAPH CONJECTURE ON PARTICULAR CLASSES OF GRAPHS

MIHAI TALMACIU

“Vasile Alecsandri" University of Bacău, Faculty of Sciences, Department of Mathemat-ics, Informatics and Educational Sciences, Calea Mărăşeşti 157, Bacău 600115, Roma-nia, e-mail: mtalmaciu@ub.ro, mihaitalmaciu@yahoo.com

Abstract

A graph is normal if there exists a cross-intersecting pair of set families one of which consists of cliques while the other one consists of stable sets, and furthermore every vertex is obtained as one of these intersections. It is known that perfect graphs are normal. Korner and de Simone observed that , and are minimal not normal and conjectured, as generalization of the Strong Perfect Graph Theorem, that every ( , , )-free graph is normal (Normal Graph Conjecture). In this paper we prove this conjecture for the class of minimal Asteroidal Triple (AT) graphs.

Keywords

Asteroidal triple graph normal graph weakly decomposition recognition algorithm