| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 9514543 | Electronic Notes in Discrete Mathematics | 2005 | 4 Pages |
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. 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. Another open question concerning clique-perfect graphs is the complexity of the recognition problem. In this work we characterize clique-perfect graphs by a restricted list of minimal forbidden induced subgraphs when the graph is a Helly circular-arc graph. This characterization leads to a polynomial time recognition algorithm for clique-perfect graphs inside this class of graphs.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Flavia Bonomo, Guillermo Durán,