Colouring non-even digraphs

DOI10.37236/8800zbMATH Open1503.05044arXiv1903.02872OpenAlexW2981636527MaRDI QIDQ2094875FDOQ2094875

Raphael Steiner, Marcelo Garlet Millani, Sebastian Wiederrecht

Publication date: 8 November 2022

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

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.

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

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

zbMATH Keywords

digraphsNP-hardnessvertex coloringdichromatic number

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On a conjecture of Lovász concerning bricks. I: The characteristic of a matching covered graph
• Pólya's permanent problem
• A characterization of convertible (0,1)-matrices
• Permanents, Pfaffian orientations, and even directed circuits
• The complexity of computing the permanent
• Which problems have strongly exponential complexity?
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Über eine Eigenschaft der ebenen Komplexe
• On the complexity of \(k\)-SAT
• On n-extendable graphs
• The dichromatic number of a digraph
• A Minimax Theorem for Directed Graphs
• Combinatorial optimization. Packing and covering
• Matching structure and the matching lattice
• Star chromatic number
• Cover-Decomposition and Polychromatic Numbers
• Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs
• Acyclic Homomorphisms and Circular Colorings of Digraphs
• \(K_4\)-free and \(\overline{C_6}\)-free planar matching covered graphs
• Planar Digraphs of Digirth Four are 2-Colorable
• \(M\)-alternating paths in \(n\)-extendable bipartite graphs
• Characterization of even directed graphs
• Even dicycles
• On the width-length inequality
• Packing directed circuits exactly
• Thin edges in braces
• DICHROMATIC NUMBER AND FRACTIONAL CHROMATIC NUMBER
• On Two Unsolved Problems Concerning Matching Covered Graphs
• List coloring digraphs
• The star dichromatic number

Cited In (5)

• Title not available (Why is that?)
• Digraph coloring and distance to acyclicity
• Harmonious colorings of digraphs.
• List coloring digraphs
• Majority colourings of digraphs

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)