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.
@article{10_37236_8800,
author = {Marcelo Garlet Millani and Raphael Steiner and Sebastian Wiederrecht},
title = {Colouring non-even digraphs},
journal = {The electronic journal of combinatorics},
year = {2022},
volume = {29},
number = {4},
doi = {10.37236/8800},
zbl = {1503.05044},
url = {http://geodesic.mathdoc.fr/articles/10.37236/8800/}
}
TY - JOUR
AU - Marcelo Garlet Millani
AU - Raphael Steiner
AU - Sebastian Wiederrecht
TI - Colouring non-even digraphs
JO - The electronic journal of combinatorics
PY - 2022
VL - 29
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/8800/
DO - 10.37236/8800
ID - 10_37236_8800
ER -
