Quick search
Go!

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

Issue:

SSRSMI, Number 1, Volume XXIII

Section:

Volume 23, Number 1

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.

Code [ID]:

SSRSMI201323V23S01A0021 [0003838]

DOI:

Full paper:

Download pdf