Hell, Pavol; Mishra, Aurosish Small \(H\)-coloring problems for bounded degree digraphs. (English) Zbl 1382.68111 Du, Ding-Zhu (ed.) et al., Computing and combinatorics. 19th international conference, COCOON 2013, Hangzhou, China, June 21–23, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-38767-8/pbk). Lecture Notes in Computer Science 7936, 579-590 (2013). Summary: An NP-complete coloring or homomorphism problem may become polynomial time solvable when restricted to graphs with degrees bounded by a small number, but remain NP-complete if the bound is higher. For instance, 3-colorability of graphs with degrees bounded by 3 can be decided by Brooks’ theorem, while for graphs with degrees bounded by 4, the 3-colorability problem is NP-complete. We investigate an analogous phenomenon for digraphs, focusing on the three smallest digraphs \(H\) with NP-complete \(H\)-colorability problems. It turns out that in all three cases the \(H\)-coloring problem is polynomial time solvable for digraphs with in-degrees at most 1, regardless of the out-degree bound (respectively with out-degrees at most 1, regardless of the in-degree bound). On the other hand, as soon as both in- and out-degrees are bounded by constants greater than or equal to 2, all three problems are again NP-complete. A conjecture proposed for graphs \(H\) by T. Feder et al. [Discrete Math. 307, No. 3–5, 386–392 (2007; Zbl 1111.05035)] states that any variant of the \(H\)-coloring problem which is NP-complete without degree constraints is also NP-complete with degree constraints, provided the degree bounds are high enough. Thus, our results verify the conjecture with very precise bounds on both in- and out-degrees that are needed for NP-completeness; in particular, the bounds underscore the fact that the sufficiently large bound must apply to both the in-degrees and the out-degrees.For the entire collection see [Zbl 1263.68016]. Cited in 1 Document MSC: 68Q25 Analysis of algorithms and problem complexity 05C15 Coloring of graphs and hypergraphs Citations:Zbl 1111.05035 PDFBibTeX XMLCite \textit{P. Hell} and \textit{A. Mishra}, Lect. Notes Comput. Sci. 7936, 579--590 (2013; Zbl 1382.68111) Full Text: DOI arXiv