05920426

j

05920426 Marx, D\'aniel Complexity of clique coloring and related problems. Theor. Comput. Sci. 412, No. 29, 3487-3500 (2011). 2011 Elsevier Science Publishers, Amsterdam EN clique coloring choosability complexity polynomial hierarchy

doi:10.1016/j.tcs.2011.02.038

Summary: 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\geq 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\geq 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\geq 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.