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

FLAVIA BONOMO; GUILLERMO DURÁN; FRANCISCO J. SOULIGNAC; GABRIEL SUEIRO

Electronic Notes in Discrete Mathematics

Elsevier

Lugar: Amsterdam; Año: 2008 vol. 30 p. 51 - 56

1571-0653

A graph is clique-perfect if the cardinality of a maximum clique-independent set equals the cardinality of a minimum clique-transversal, for all its induced subgraphs. A graph G is coordinated if the chromatic number of the clique graph of H 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 cliqueperfect 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,W4,bull}-free, two superclasses of triangle-free graphs.