Colouring non-even digraphs

DOI10.37236/8800zbMath1503.05044arXiv1903.02872OpenAlexW2981636527MaRDI QIDQ2094875

Raphael Steiner, Marcelo Garlet Millani, Sebastian Wiederrecht

Publication date: 8 November 2022

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

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

zbMATH Keywords

digraphsvertex coloringNP-hardnessdichromatic number

Mathematics Subject Classification ID

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

Cites Work

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

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