Complexity of clique coloring and related problems

A k-clique-coloring of a graph G is an assignment of k colors to the vertices of G such that every maximal (i.e., not extendable) clique of G contains two vertices with different colors. We show that deciding whether a graph has a k-clique-coloring is Sigma(p)(2)-complete for every k >= 2. The complexity of two related problems are also considered. A graph is k-clique-choosable, if for every k-list-assignment on the vertices, there is a clique coloring where each vertex receives a color from its list. This problem turns out to be Pi(p)(3)-complete for every k >= 2. A graph G is hereditary k-clique-colorable if every induced subgraph of G is k-clique-colorable. We prove that deciding hereditary k-clique-colorability is also Pi(p)(3)-complete for every k >= 3. Therefore, for all the problems considered in the paper, the obvious upper bound on the complexity turns out to be the exact class where the problem belongs. (C) 2011 Elsevier B.V. All rights reserved.