On the computational complexity of the forcing chromatic number
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-x(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 F-x(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-x(G) <= 2 is US-hard with respect to polynomial-time many-one reductions. Moreover, this problem is coNP-hard even under the promises that F-x(G) <= 3 and G is 3-chromatic. On the other hand, recognizing whether F-x(G) <= 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.
computational complexity complexity classes combinatorial forcing chromatic number of a graph unique satisfiability