Colouring Non-Even Digraphs

Abstract

A colouring of a digraph as defined by Neumann-Lara in 1982 is a vertex-colouring such that no monochromatic directed cycles exist. The minimal number of colours required for such a colouring of a loopless digraph is defined to be its dichromatic number. This quantity has been widely studied in the last decades and can be considered as a natural directed analogue of the chromatic number of a graph. A digraph $D$ is called even if for every $0$-$1$-weighting of the edges it contains a directed cycle of even total weight. We show that every non-even digraph has dichromatic number at most $2$ and an optimal colouring can be found in polynomial time. We strengthen a previously known NP-hardness result by showing that deciding whether a directed graph is $2$-colourable remains NP-hard even if it contains a feedback vertex set of bounded size.