Complexity of fractional dichromatic number ≤ p

AX_fractional_dichromatic_number_complexity

Source: arXiv:1812.02420 — On the Complexity of Digraph Colourings and Vertex Arboricity

Problem 3.21 · arXiv:1812.02420

arXiv Problem high confidence— first stated 2020-01-09

Authors: Winfried Hochstättler, Felix Schröder, Raphael Steiner

Status ai-proved high confidence

For digraphs allowing digons, the p=2 problem is NP-complete via a two-layer construction in which matching digons force every weight-2 fractional colouring to encode an ordinary acyclic 2-colouring.

Auto-reviewed 2026-09-01 with gpt-5.6-sol.

AI-generated write-up ai-proved

Open the PDF write-up

This is a model-generated research artifact, not a peer-reviewed publication or a formally verified proof.

Problem. Let $p\geq 1$ be a fixed real number. Instance: A (multi-)digraph $D$. Decide whether $\vec{\chi}_{f}(D)\leq 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