×

Acyclic homomorphisms and circular colorings of digraphs. (English) Zbl 1034.05022

An acyclic homomorphism of a digraph \(D\) into a digraph \(F\) is a mapping \(\phi: V(D) \to V(F)\) such that (i) for every arc \(uv \in E(D)\), either \(\phi(u)=\phi(v)\) or \(\phi(u)\phi(v)\) is an arc of \(F\) and (ii) for every vertex \(v\in V(F)\), the subgraph of \(D\) induced by \(\phi^{-1}(v)\) is acyclic.
The digraph \(\vec C(k,d)\) has the vertex set \(V(\vec C(k,d))=\{0,\dots,k-1\}\), and from each vertex \(i\in V(\vec C(k,d))\) there are arcs to \(i+d\), \(i+d+1,\dots,i+k-1\), with arithmetic modulo \(k\). (Notice that \(\vec C(n,n-1)\simeq \vec C_n\) is the directed \(n\)-cycle.) The circular chromatic number \(\chi_c(D)\) of the digraph \(D\) is the minimum of all rational numbers \(k/d\) (where \(k\) and \(d\leq k\) are positive integers) such that there exists an acyclic homomorphism \(D\to \vec C(k,d)\). If \(k\) and \(d\) are positive integers with \(k\geq d\), then \(\chi_c(\vec C(k,d))=\frac kd\).
In this paper it is proved that the acyclic \(F\)-coloring problem is NP-complete, unless \(F\) is acyclic, in which case it is polynomial time solvable. This implies, in particular, that to decide if \(\chi_c(D)\leq d\) is also NP-complete for every fixed rational number \(d>1\).

MSC:

05C15 Coloring of graphs and hypergraphs
05C20 Directed graphs (digraphs), tournaments
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI