On the Computational Complexity of the Forcing Chromatic Number

Details On the Computational Complexity of the Forcing Chromatic Number On the Computational Complexity of the Forcing Chromatic Number

2004-06-23

arxiv.org/abs/cs/0406044v4

Computer Science

Computational Complexity

24 pages; This is the final version

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On the Computational Complexity of the Forcing Chromatic Number does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Computational Complexity of the Forcing Chromatic Number, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Computational Complexity of the Forcing Chromatic Number will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-247532