NP-hardness of the recognition of coordinated graphs

FRANCISCO J. SOULIGNAC; GABRIEL SUEIRO

ANNALS OF OPERATIONS RESEARCH

SPRINGER

Año: 2009 vol. 169 p. 17 - 34

0254-5330

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. In previous works, polynomial time algorithms were found for recognizing coordinated graphs within some classes of graphs. In this paper we prove that the recognition problem for coordinated graphs is NP-hard, and it is NP-complete even when restricted to the class of {gem, C 4, odd hole}-free graphs with maximum degree four, maximum clique size three and at most three cliques sharing a common vertex.