info:eu-repo/semantics/article
On some graph classes related to perfect graphs: A survey
Fecha
2020-07-15Registro en:
Bonomo-Braberman, Flavia; Durán, Guillermo; Safe, Martin Dario; Wagler, Annegret K.; On some graph classes related to perfect graphs: A survey; Elsevier Science; Discrete Applied Mathematics; 281; 15-7-2020; 42-60
0166-218X
CONICET Digital
CONICET
Autor
Bonomo-Braberman, Flavia
Durán, Guillermo
Safe, Martin Dario
Wagler, Annegret K.
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.
Ítems relacionados
Mostrando ítems relacionados por Título, autor o materia.
-
Coordinated graphs and clique graphs of clique-Helly perfect graphs
Bonomo, Flavia; Durán Maggiolo, Guillermo; Groshaus, Marina (2007)A new class of graphs related to perfect graphs is defined in this work: coordinated graphs. A graph G is coordinated if the cardinality of a maximum set of cliques of H with a common vertex is equal to the cardinality of ... -
On clique-perfect and k-perfect graphs
Autor desconocido (DEPT. OF COMBINATORICS AND OPTIMIZATION, UNIVERSITY OF WATERLOO, 2006) -
On clique-perfect and k-perfect graphs
Autor desconocido (DEPT. OF COMBINATORICS AND OPTIMIZATION, UNIVERSITY OF WATERLOO, 2006)