NP-hardness of the recognition of coordinated graphs

FRANCISCO SOULIGNAC; GABRIEL SUEIRO

Montevideo

Congreso; XIII Congreso Latino-Iberoamericano de Investigación Operativa (XIII CLAIO); 2006

Universidad de la República

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. In a previous work, 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 remains NP-complete even restricted to the class of {gem, C4 }-free graphs with maximum degree 4, maximum clique size 3 and at most three cliques sharing a common vertex.