NP-completeness of circular F-coloring
Conjecture 2.16 · arXiv:1812.02420
Status partial high confidence
Conjecture 2.16 asserts NP-completeness of circular F-colouring for every digraph F containing a directed cycle. Theorem 2.17 in the same paper confirms the conjecture for all such F that are digon-free, have an odd cycle in their symmetric part, or are 2-colourable. The sole remaining open case is F containing a directed cycle whose symmetric part is non-empty, bipartite, and such that F is not 2-colourable; no subsequent work resolving this case was found in the literature.
Reviewer notes. Theorem 2.17 within the source paper already settles the conjecture for almost all cases; the single remaining open case involves F with a directed cycle, a non-empty bipartite symmetric part, and chromatic number > 2. A wide web search (5 calls) returned no follow-up paper addressing this residual case.
Context
The authors conjecture that, under the assumption $\mathsf{P}\neq\mathsf{NP}$, the only polynomially solvable instances of Problem 2.15 are those where $F$ is acyclic (for which only acyclic digraphs map circularly to $F$). Theorem 2.17 confirms this conjecture for almost all cases.
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