On graph classes related to perfect graphs: A survey
BONOMO, FLAVIA; DURÁN, GUILLERMO; MARTÍN DARÍO SAFE; WAGLER, ANNEGRET KATRIN
DISCRETE APPLIED MATHEMATICS
ELSEVIER SCIENCE BV
Lugar: Amsterdam; Año: 2020 vol. 281 p. 42 - 60
Perfect graphs form a well-known class of graphs introduced by Berge in the 1960s in terms of a min-max type equality involving two famous graph parameters. In this work, we survey certain variants and subclasses of perfect graphs defined by means of min-max relations of other graph parameters; namely: clique-perfect, coordinated, and neighborhood-perfect graphs. We show the connection between graph classes and both hypergraph theory, the clique graph operator, and some other graph classes. We review different partial characterizations of them by forbidden induced subgraphs, present the previous results, and the main open problems. Computational complexity problems are also discussed.