Complexity of Σ-k-dicolourability k∈{4,5}
Problem 4.4 · arXiv:2102.01034
Status open high confidence
Problem 4.4 from arXiv:2102.01034 asks for the computational complexity of \Sigma-k-DICOLOURABILITY for k \in {4, 5} and \Sigma different from the sphere; the source paper establishes NP-completeness for k=2 and polynomial-time solvability for k \geq 6, leaving the intermediate cases k=4 and k=5 explicitly open. A wide literature search found no follow-up paper that resolves (or even substantially advances) this complexity question for either value of k on any non-spherical surface. The problem remains open as of May 2026.
Reviewer notes. No follow-up found. Five web calls were used (2 WebSearch + 3 WebFetch). The paper was published in the Electronic Journal of Combinatorics (2022, v29i1p30). The open problem is sandwiched between the known NP-complete case k=2 and the known polynomial-time case k>=6; resolving k in {4,5} likely requires new structural insight into digraphs on surfaces. The thesis 'Digraph colouring' (HAL tel-04633967, 2024) appeared in the search but was access-denied; it may contain partial progress and warrants manual inspection.
Context
The paper establishes that Σ-2-DICOLOURABILITY is NP-complete for any surface, and that Σ-k-DICOLOURABILITY is polynomial-time solvable for any surface Σ and any integer k ≥ 6. The complexity for k ∈ {4, 5} on surfaces other than the sphere is explicitly left open.
Notes. Problem 4.4 is referenced in the introduction but the full text of Section 4 was not present in the PDF extraction; the statement is inferred from the surrounding context.
Source paper
On the dichromatic number of surfaces
Pierre Aboulker, Frédéric Havet, Kolja Knauer, Clément Rambaud · 2021-11-16
https://arxiv.org/abs/2102.01034
PDF source