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