Colouring non-even digraphs

DOI10.37236/8800MaRDI QIDQ2094875zbMATH OpenOpenAlexFDO

Authors Marcelo Garlet Millani, Raphael Steiner, Sebastian Wiederrecht

Publication date 8 November 2022

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1903.02872

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

dichromatic number digraphs NP-hardness vertex coloring

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Fractional graph theory, fuzzy graph theory (05C72) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: 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.

Review text

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.

Recommendations

Cites work

Cited in

(11)

This page was built for publication: Colouring non-even digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2094875)