TY - GEN A1 - Wagler, Annegret T1 - The Normal Graph Conjecture is true for Circulants N2 - Normal graphs are defined in terms of cross-intersecting set families: a graph is normal if it admits a clique cover $\cal Q$ and a stable set cover $\cal S$ s.t.~every clique in $\cal Q$ intersects every stable set in $\cal S$. Normal graphs can be considered as closure of perfect graphs by means of co-normal products (Körner 1973) and graph entropy (Czisz\'ar et al. 1990). Perfect graphs have been recently characterized as those graphs without odd holes and odd antiholes as induced subgraphs (Strong Perfect Graph Theorem, Chudnovsky et al. 2002). Körner and de Simone observed that $C_5$, $C_7$, and $\overline C_7$ are minimal not normal and conjectured, as generalization of the Strong Perfect Graph Theorem, that every $C_5$, $C_7$, $\overline C_7$- free graph is normal (Normal Graph Conjecture, Körner and de Simone 1999). We prove this conjecture for a first class of graphs that generalize both odd holes and odd antiholes, the circulants, by characterizing all the normal circulants. T3 - ZIB-Report - 04-06 KW - perfect graphs KW - normal graphs KW - circulants Y1 - 2004 UR - https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/781 UR - https://nbn-resolving.org/urn:nbn:de:0297-zib-7813 ER -