On some graph classes related to perfect graphs: A survey

Abstract

© 2019 Elsevier B.V.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.