Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs

BONOMO, FLAVIA; DURÁN, GUILLERMO; SOULIGNAC, FRANCISCO JUAN; SUEIRO, GABRIEL

DISCRETE APPLIED MATHEMATICS

Elsevier

Año: 2009 vol. 157 p. 3511 - 3518

0166-218X

A graph G is clique-perfect if the cardinality of a maximum clique-independent set of H equals the cardinality of a minimum clique-transversal of H, for every induced subgraph H of G. A graph G is coordinated if the minimum number of colors that can be assigned to the cliques of H in such a way that no two cliques with non-empty intersection receive the same color equals the maximum number of cliques of H with a common vertex, for every induced subgraph H of G. 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,W_4,bull}-free, both superclasses of triangle-free graphs.