Acyclic Homomorphisms and Circular Colorings of Digraphs
Tomás Feder, Pavol Hell, Bojan Mohar · SIAM Journal on Discrete Mathematics · 2003
An acyclic homomorphism of a digraph D into a digraph F is a mapping $\phi\colon V(D) \to V(F)$ such that for every arc $uv\in E(D)$, either $\phi(u)=\phi(v)$ or $\phi(u)\phi(v)$ is an arc of F, and for every vertex $v\in V(F)$, the subgraph of D induced on $\phi^{-1}(v)$ is acyclic. For each fixed digraph F we consider the following decision problem: Does a given input digraph D admit an acyclic homomorphism to F? We prove that this problem is NP-complete unless F is acyclic, in which case it is polynomial time solvable. From this we conclude that it is NP-complete to decide if the circular chromatic number of a given digraph is at most q, for any rational number $q > 1$. We discuss the complexity of the problems restricted to planar graphs. We also refine the proof to deduce that certain F-coloring problems are NP-complete.