  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(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(G)$ relating it to the complexity class US
introduced by Blass and Gurevich. We prove that recognizing if $F(G)\le 2$ is
US-hard with respect to polynomial-time many-one reductions. Moreover, this
problem is coNP-hard even under the promises that $F(G)\le 3$ and $G$ is
3-chromatic. On the other hand, recognizing if $F(G)\le k$, for each constant
$k$, is reducible to a problem in US via disjunctive truth-table reduction.
  Similar results are obtained also for forcing variants of the clique and the
domination numbers of a graph.
