INVESTIGADORES
DURAN Guillermo Alfredo
artículos
Título:
Partial characterizations of clique-perfect graphs
Autor/es:
BONOMO, FLAVIA; CHUDNOVSKY, MARIA; DURAN, GUILLERMO ALFREDO
Revista:
Electronic Notes in Discrete Mathematics
Referencias:
Año: 2005 vol. 19 p. 95 - 101
ISSN:
1571-0653
Resumen:
Abstract: A clique-transversal of a graph G is a subset of vertices that meets all the cliques of G. A clique-independent set is a collection of pairwise vertex-disjoint cliques. The clique-transversal number and clique-independence number of G are the sizes of a minimum clique-transversal and a maximum clique-independent set of G, respectively. A graph G is clique-perfect if the sizes of a minimum clique-transversal and a maximum clique-independent set are equal for every induced subgraph of G. The list of minimal forbidden induced subgraphs for the class of clique-perfect graphs is not known. In this paper, we present a partial result in this direction, that is, we characterize clique-perfect graphs by a restricted list of forbidden induced subgraphs when the graph belongs to a certain class.
