Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1137/050641594 | Clinical Orthopaedics and Related Research |
Keywords | DocType | Volume |
vertex colorings,domination number,adjacent vertex,chromatic number,forcing chromatic number,chromatic graph,remaining vertex,disjunctive truth-table reduction,computational complexity,complexity class,smallest number,polynomial time | Journal | 37 |
Issue | ISSN | Citations |
1 | 0302-9743 | 4 |
PageRank | References | Authors |
0.59 | 25 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Frank Harary | 1 | 907 | 270.87 |
| Wolfgang Slany | 2 | 329 | 49.70 |
| Oleg Verbitsky | 3 | 191 | 27.50 |