On the Complexity of Digraph Colourings and Vertex Arboricity
From MaRDI portal
Publication:5130735
DOI10.23638/DMTCS-22-1-4zbMath1452.05061arXiv1812.02420MaRDI QIDQ5130735
Winfried Hochstättler, Felix Schröder, Raphael Steiner
Publication date: 28 October 2020
Full work available at URL: https://arxiv.org/abs/1812.02420
computational complexitycircular vertex arboricityfractional dichromatic numberstar dichromatic number
Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Cyclic orderings and cyclic arboricity of matroids
- On the complexity of \(H\)-colouring planar graphs
- On the complexity of H-coloring
- The dichromatic number of a digraph
- Circular vertex arboricity
- A flow theory for the dichromatic number
- The point-arboricity of a graph
- DICHROMATIC NUMBER AND FRACTIONAL CHROMATIC NUMBER
- Uniquely D-colourable Digraphs with Large Girth
- Star chromatic number
- Acyclic Homomorphisms and Circular Colorings of Digraphs
- The circular chromatic number of a digraph
- A Note on the Vertex Arboricity of a Graph