A construction of uniquely \(n\)-colorable digraphs with arbitrarily large digirth (Q528972)

Summary: A natural digraph analogue of the graph-theoretic concept of an `independent set' is that of an `acyclic set', namely a set of vertices not spanning a directed cycle. Hence a digraph analogue of a graph coloring is a decomposition of the vertex set into acyclic sets and we say a digraph is uniquely \(n\)-colorable when this decomposition is unique up to relabeling. It was shown probabilistically in [\textit{A. Harutyunyan} et al., Can. J. Math. 64, No. 6, 1310--1328 (2012; Zbl 1254.05057)] that there exist uniquely \(n\)-colorable digraphs with arbitrarily large girth. Here we give a construction of such digraphs and prove that they have circular chromatic number \(n\). The graph-theoretic notion of `homomorphism' also gives rise to a digraph analogue. An acyclic homomorphism from a digraph \(D\) to a digraph \(H\) is a mapping \(\phi: V(D) \rightarrow V(H)\) such that \(uv \in A(D)\) implies that either \(\phi(u)\phi(v) \in A(H)\) or \(\phi(u)=\phi(v)\), and all the `fibers' \(\phi^{-1}(v)\), for \(v \in V(H)\), of \(\phi\) are acyclic. In this language, a core is a digraph \(D\) for which there does not exist an acyclic homomorphism from \(D\) to a proper subdigraph of itself. Here we prove some basic results about digraph cores and construct highly chromatic cores without short cycles.