Circular F-colourability complexity dichotomy
Problem 2.15 · arXiv:1812.02420
Status partial medium confidence
Problem 2.15 asks for the complexity of deciding circular F-colourability for a fixed digraph F. Conjecture 2.16 (stated in the same paper) asserts this problem is NP-complete whenever F contains a directed cycle. Theorem 2.17 of the source paper already establishes NP-completeness for almost all such F: specifically for digon-free digraphs with directed cycles, digraphs whose symmetric part contains an odd cycle, and 2-colourable digraphs. The remaining open case is digraphs F that contain a directed cycle whose symmetric part is non-empty and bipartite. No external follow-up paper resolving the full conjecture was found in the literature.
Reviewer notes. The source paper (arXiv:1812.02420, published DMTCS 2020) itself partially resolves the conjecture via Theorem 2.17, proving NP-completeness for three broad families of F. The open subcase involves digraphs F with a directed cycle and a non-empty bipartite symmetric part. No follow-up paper fully resolving Problem 2.15 / Conjecture 2.16 was found after 4 web searches and targeted fetches.
Context
A digraph $D$ is circularly $F$-colourable if there exists a circular homomorphism from $D$ to $F$. This problem generalises Problem 1 and serves as a directed analogue of the $H$-colouring problem for graphs. Conjecture 2.16 asserts that NP-completeness holds whenever $F$ contains a directed cycle, and Theorem 2.17 establishes this for almost all such cases.
Notes. The complete dichotomy (all F with a directed cycle) is conjectured but not fully proved within the paper.
Source paper
On the Complexity of Digraph Colourings and Vertex Arboricity
Winfried Hochstättler, Felix Schröder, Raphael Steiner · 2020-01-09
https://arxiv.org/abs/1812.02420