Partial characterizations of coordinated graphs

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

Rio de Janeiro

Simposio; 19th international symposium on mathematical programming; 2006

A graph G is coordinated if the minimum numbers of colors that can be assigned to the cliques of H in such a way that no two cliques with nonempty intersection receive the same color is equal to 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 list of minimal forbidden induced subgraphs for the class of coordinated graphs is not known.  In this paper, we present a partial solution in this direction, that is, we characterize coordinated graphs by minimal forbidden induced subgraphs when the graph is either a line graph, or paw-free, or {W4, gem, bull}-free, or the complement of a forest.