On the Complexity of Digraph Colourings and Vertex Arboricity

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

It has been shown by Bokal et al. that deciding 2-colourability of digraphs is an NP-complete problem. This result was later on extended by Feder et al. to prove that deciding whet…