Colouring non-even digraphs (Q2094875)

It is known that the four-colour problem is one of the hardest challenges in graph theory and it was settled positively by \textit{K. Appel} and \textit{W. Haken} [Ill. J. Math. 21, 429--490 (1977; Zbl 0387.05009); ibid. 21, 491--567 (1977; Zbl 0387.05010)]. The corresponding task for the graphs with direction for their edges is the two-colour problem raised independently by Erdős and Skrekovski and is still open today. A digraph \(D\) is called oriented if its underlying undirected graph is simple. The two-color problem statement is: Every oriented planar digraph \(D\) is 2-colourable. A substantial development towards the solution of this task is the effort by \textit{Z. Li} and \textit{B. Mohar} [SIAM J. Discrete Math. 31, No. 3, 2201--2205 (2017; Zbl 1371.05089)], who proved that every oriented planar digraph of girth at least 4 is 2-colourable. A digraph \(D\) is said to be even if for every 0-1-weighting of the edges it contains a directed cycle of even total weight. The authors in this article prove that every non-even digraph has a dichromatic number at most 2 and an optimal colouring can be found in polynomial time. By doing this they further strengthen a known NP-hardness result by establishing that the task of deciding whether a directed graph is 2-colourable remains NP-hard even if it contains a feedback vertex set of bounded size. The proof techniques adopted here are mind-boggling and open a plethora of ideas for vibrant research work on this topic for more years to come in the future.