Can I read Colouring Non-Even Digraphs on EtoBox?

Colouring Non-Even Digraphs by Millani, Marcelo Garlet; Steiner, Raphael; Wiederrecht, Sebastian is a scholarly article available to read on EtoBox.

What is Colouring Non-Even Digraphs about?

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.

Author

Millani, Marcelo Garlet; Steiner, Raphael; Wiederrecht, Sebastian

Published

2019

Language

EN