On the Computational Complexity of the Forcing Chromatic Number
Frank Harary, Wolfgang Slany, Oleg Verbitsky · SIAM Journal on Computing · 2007
We consider vertex colorings of graphs in which adjacent vertices have distinct colors. A graph is s‐chromatic if it is colorable in s colors and any coloring of it uses at least s colors. The forcing chromatic number $F_{\chi}(G)$ of an s‐chromatic graph G is the smallest number of vertices which must be colored so that, with the restriction that s colors are used, every remaining vertex has its color determined uniquely. We estimate the computational complexity of $\force G$ relating it to the complexity class US introduced by Blass and Gurevich [Inform. Control, 55 (1982), pp. 80–88]. We prove that recognizing whether $F_{\chi}(G)\le2$ is US‐hard with respect to polynomial‐time many‐one reductions. Moreover, this problem is coNP‐hard even under the promises that $F_{\chi}(G)\le3$ and G is 3‐chromatic. On the other hand, recognizing whether $F_{\chi}(G)\le k$, for each constant k, is reducible to a problem in US via a disjunctive truth‐table reduction. Similar results are obtained also for forcing variants of the clique and the domination numbers of a graph.