Acyclic Homomorphisms and Circular Colorings of Digraphs
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\).
- Paths, cycles and circular colorings in digraphs
- On the complexity of H-colouring planar graphs
- Homomorphisms to powers of digraphs
- The star dichromatic number
- Colouring non-even digraphs
- Homomorphisms to digraphs with large girth and oriented colorings of minimal series-parallel digraphs
- Convex circuit-free coloration of an oriented graph
- The circular chromatic number of a digraph
- Colouring, constraint satisfaction, and complexity
- On the complexity of digraph colourings and vertex arboricity
- Constraint Satisfaction Problems with Infinite Templates
- Acyclic coloring of products of digraphs
- Colouring non-even digraphs
- Homomorphisms of (n,m)-graphs with respect to generalised switch
- \(H\)-coloring degree-bounded (acyclic) digraphs
- Acyclic coloring parameterized by directed clique-width
This page was built for publication: Acyclic Homomorphisms and Circular Colorings of Digraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4443128)
