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 -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 -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 -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.