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.
Cuvinte cheie
Asteroidal triple graph
normal graph
weakly decomposition
recognition algorithm