On clique-perfect and k-perfect graphs

Abstract

A graph G is clique-perfect if the cardinality of a maximum clique-independent set of H is equal to the cardinality of a minimum clique-transversal 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, Kperfect, clique-perfect and c–clique-perfect graphs. Besides, partial characterizations of K-perfect graphs using polyhedral theory and clique subgraphs are formulated.