Acyclic Homomorphisms and Circular Colorings of Digraphs
From MaRDI portal
Publication:4443128
DOI10.1137/S0895480103422184zbMath1034.05022OpenAlexW2013164124MaRDI QIDQ4443128
Bojan Mohar, Tomás Feder, Pavol Hell
Publication date: 8 January 2004
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0895480103422184
digraphcircular chromatic numberNP-completenessgraph homomorphismcircular coloringacyclic homomorphism
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 (10)
Acyclic coloring parameterized by directed clique-width ⋮ Acyclic coloring of products of digraphs ⋮ Colouring, constraint satisfaction, and complexity ⋮ On the Complexity of Digraph Colourings and Vertex Arboricity ⋮ Convex circuit-free coloration of an oriented graph ⋮ Paths, cycles and circular colorings in digraphs ⋮ The star dichromatic number ⋮ On the complexity of \(H\)-colouring planar graphs ⋮ Constraint Satisfaction Problems with Infinite Templates ⋮ Colouring non-even digraphs
This page was built for publication: Acyclic Homomorphisms and Circular Colorings of Digraphs
