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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 1058-1082 |
| Number of pages | 25 |
| Journal | Discrete Applied Mathematics |
| Volume | 156 |
| Issue number | 7 |
| DOIs | |
| State | Published - Apr 1 2008 |
| Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics
- Applied Mathematics
Keywords
- Claw-free graphs
- Clique-perfect graphs
- Hereditary clique-Helly graphs
- Line graphs
- Perfect graphs