  A colouring of a digraph as defined by Erdos and Neumann-Lara in 1980 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.
