| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 420472 | Discrete Applied Mathematics | 2009 | 8 Pages |
A graph GG is clique-perfect if the cardinality of a maximum clique-independent set of HH equals the cardinality of a minimum clique-transversal of HH, for every induced subgraph HH of GG. A graph GG is coordinated if the minimum number of colors that can be assigned to the cliques of HH in such a way that no two cliques with non-empty intersection receive the same color equals the maximum number of cliques of HH with a common vertex, for every induced subgraph HH of GG. Coordinated graphs are a subclass of perfect graphs. The complete lists of minimal forbidden induced subgraphs for the classes of clique-perfect and coordinated graphs are not known, but some partial characterizations have been obtained. In this paper, we characterize clique-perfect and coordinated graphs by minimal forbidden induced subgraphs when the graph is either paw-free or {gem, W4W4, bull}-free, both superclasses of triangle-free graphs.
