Autor(es)

Flavio Bonomo and Guillermo Durán and Marina Groshaus and Jayme L Szwarcfiter

URL Pública

Abstract

A graph G is clique-perfect if the cardinality of a maximum cliqueindependent set of H is equal to the cardinality of a minimum cliquetransversal of H, for every induced subgraph H of G. When equality holds for every clique subgraph of G, the graph is c–clique-perfect. A graph G is K-perfect when its clique graph K (G) is perfect. In this work, relations are described among the classes of perfect, K-perfect, clique-perfect and c–clique-perfect graphs. Besides, partial characterizations of K-perfect graphs using polyhedral theory and clique subgraphs are formulated.