Name
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. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.37236/8800 | ELECTRONIC JOURNAL OF COMBINATORICS |
DocType | Volume | Issue |
Journal | 29 | 4 |
ISSN | Citations | PageRank |
1077-8926 | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marcelo Garlet Millani | 1 | 0 | 0.34 |
| Raphael Steiner | 2 | 0 | 1.01 |
| Sebastian Wiederrecht | 3 | 0 | 0.34 |