Author | dc.contributor.author | Bonomo, Flavia | |
Author | dc.contributor.author | Chudnovsky, Maria | es_CL |
Author | dc.contributor.author | Durán Maggiolo, Guillermo | es_CL |
Admission date | dc.date.accessioned | 2010-01-11T16:19:56Z | |
Available date | dc.date.available | 2010-01-11T16:19:56Z | |
Publication date | dc.date.issued | 2008-04-01T18:52:54Z | |
Cita de ítem | dc.identifier.citation | DISCRETE APPLIED MATHEMATICS Volume: 156 Issue: 7 Pages: 1058-1082 Published: APR 1 2008 | en_US |
Identifier | dc.identifier.issn | 0166-218X | |
Identifier | dc.identifier.other | 10.1016/j.dam.2007.05.048 | |
Identifier | dc.identifier.uri | https://repositorio.uchile.cl/handle/2250/125073 | |
Abstract | dc.description.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 these two numbers 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 two different subclasses of claw-free graphs. | en_US |
Lenguage | dc.language.iso | en | en_US |
Publisher | dc.publisher | ELSEVIER | en_US |
Keywords | dc.subject | ALGORITHMIC ASPECTS | en_US |
Título | dc.title | Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs | en_US |
Document type | dc.type | Artículo de revista | |