On the Computational Complexity of the Forcing Chromatic Number

Original · EN

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)≤ 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)≤ 3 and G is 3-chromatic. On the other hand, recognizing if F(G)≤ 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.