1. The Normal Graph Conjecture for Two Classes of Sparse Graphs.
- Author
-
Berry, Anne and Wagler, Annegret K.
- Subjects
- *
GRAPH theory , *SUBGRAPHS , *PATHS & cycles in graph theory , *SET theory , *ALGORITHMS - Abstract
Normal graphs are defined in terms of cross-intersecting set families: a graph is normal if it admits a clique cover Q
and a stable set cover S s.t. every clique in Q intersects every stable set in S . Normal graphs can be considered as closure of perfect graphs by means of co-normal products and graph entropy. Perfect graphs have been characterized as those graphs without odd holes and odd antiholes as induced subgraphs (Strong Perfect Graph Theorem, Chudnovsky et al.). Körner and de Simone observed that C5 , C7 , and C¯7 are minimal not normal and conjectured, in analogy to the Strong Perfect Graph Theorem, that every (C5,C7,C¯7) -free graph is normal (Normal Graph Conjecture, Körner and de Simone). Recently, this conjecture has been disproved by Harutyunyan, Pastor and Thomassé. However, in this paper we verify it for two classes of sparse graphs, 1-trees and cacti. In addition, we provide both linear time recognition algorithms and characterizations for the normal graphs within these two classes. [ABSTRACT FROM AUTHOR] - Published
- 2018
- Full Text
- View/download PDF