Partial characterizations of coordinated graphs: line graphs and complements of forests

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

MATHEMATICAL METHODS OF OPERATIONS RESEARCH (HEIDELBERG)

Springer

Año: 2009 vol. 69 p. 251 - 270

1432-2994

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 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 result in this direction, that is, we characterize coordinated graphs by minimal forbidden induced subgraphs when the graph is either a line graph, or the complement of a forest.