Colouring non-even digraphs
From MaRDI portal
Publication:2094875
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)
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 1762085 (Why is no real title available?)
- scientific article; zbMATH DE number 6116733 (Why is no real title available?)
- scientific article; zbMATH DE number 6127683 (Why is no real title available?)
- scientific article; zbMATH DE number 3326387 (Why is no real title available?)
- scientific article; zbMATH DE number 3102312 (Why is no real title available?)
- A Minimax Theorem for Directed Graphs
- A characterization of convertible (0,1)-matrices
- A survey of Pfaffian orientations of graphs
- Acyclic Homomorphisms and Circular Colorings of Digraphs
- Characterization of even directed graphs
- Combinatorial optimization. Packing and covering
- Dichromatic number and fractional chromatic number
- Even dicycles
- List coloring digraphs
- Matching structure and the matching lattice
- On a conjecture of Lovász concerning bricks. I: The characteristic of a matching covered graph
- On n-extendable graphs
- On the complexity of \(k\)-SAT
- On the width-length inequality
- On two unsolved problems concerning matching covered graphs
- Packing directed circuits exactly
- Permanents, Pfaffian orientations, and even directed circuits
- Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs
- Planar digraphs of digirth four are 2-colorable
- Pólya's permanent problem
- Star chromatic number
- The complexity of computing the permanent
- The dichromatic number of a digraph
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The star dichromatic number
- Thin edges in braces
- Which problems have strongly exponential complexity?
- \(K_4\)-free and \(\overline{C_6}\)-free planar matching covered graphs
- \(M\)-alternating paths in \(n\)-extendable bipartite graphs
- Über eine Eigenschaft der ebenen Komplexe
Cited in
(11)- Majority colourings of digraphs
- Colouring non-even digraphs
- scientific article; zbMATH DE number 5298418 (Why is no real title available?)
- Digraph coloring and distance to acyclicity
- Digraph redicolouring
- Harmonious colorings of digraphs.
- Planar digraphs of digirth five are 2-colorable
- On the dichromatic number of surfaces
- Planar digraphs of digirth four are 2-colorable
- List coloring digraphs
- Notes on weak-odd edge colorings 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)
