INVESTIGADORES
BONOMO flavia
artículos
Título:
On graph classes related to perfect graphs: A survey
Autor/es:
BONOMO, FLAVIA; DURÁN, GUILLERMO; MARTÍN DARÍO SAFE; WAGLER, ANNEGRET KATRIN
Revista:
DISCRETE APPLIED MATHEMATICS
Editorial:
ELSEVIER SCIENCE BV
Referencias:
Lugar: Amsterdam; Año: 2020 vol. 281 p. 42 - 60
ISSN:
0166-218X
Resumen:
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.