Complexity of fractional dichromatic number ≤ p
Problem 3.21 · arXiv:1812.02420
Status open high confidence
The paper proves NP-completeness of deciding $\vec{\chi}_f(D) \leq p$ for all real $p > 1$ with $p \neq 2$, leaving the case $p = 2$ explicitly open. No follow-up paper resolving the $p = 2$ case was found in any indexed source as of May 2026. The problem is analogous to the circular dichromatic number results of Feder et al., and the authors note no obvious obstruction to NP-hardness at $p = 2$ but could not establish it.
Reviewer notes. No follow-up found. The p=2 case remains the sole unresolved complexity case for the fractional dichromatic number threshold decision problem. The difficulty stems from the fact that deciding $\vec{\chi}_f(D) \leq 2$ is equivalent to a question about acyclic 2-coloring of digraphs, whose complexity is not captured by the NP-hardness reductions used for other values of p.
Context
This problem asks for the complexity of deciding whether the fractional dichromatic number of a digraph is at most $p$. The paper proves NP-completeness for all real $p>1$ with $p\neq 2$, mirroring results of Feder et al. for the circular dichromatic number; the case $p=2$ is explicitly left open.
Notes. The case $p=2$ remains unresolved after this 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