On some graph classes related to perfect graphs: A survey

dc.creatorBonomo-Braberman, Flavia
dc.creatorDurán, Guillermo
dc.creatorSafe, Martín D.
dc.creatorWagler, Annegret K.
dc.date.accessioned2019-10-11T17:30:13Z
dc.date.available2019-10-11T17:30:13Z
dc.date.created2019-10-11T17:30:13Z
dc.date.issued2020
dc.identifier0166218X
dc.identifier10.1016/j.dam.2019.05.019
dc.identifierhttps://repositorio.uchile.cl/handle/2250/171291
dc.description.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.
dc.languageen
dc.publisherElsevier B.V.
dc.rightshttp://creativecommons.org/licenses/by-nc-nd/3.0/cl/
dc.rightsAttribution-NonCommercial-NoDerivs 3.0 Chile
dc.sourceDiscrete Applied Mathematics
dc.subjectBalanced graphs
dc.subjectClique-perfect graphs
dc.subjectCoordinated graphs
dc.subjectK-perfect graphs
dc.subjectNeighborhood-perfect graphs
dc.subjectPerfect graphs
dc.titleOn some graph classes related to perfect graphs: A survey
dc.typeArtículo de revista


Este ítem pertenece a la siguiente institución