A construction of uniquely n-colorable digraphs with arbitrarily large digirth

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 [A. Harutyunyan et al., Uniquely D-colorable digraphs with large girth, Canad. J. Math., 64(6): 1310-1328, 2012] 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) -> V (H) such that uu is an element of A(D) implies that either phi(u)phi(v) is an element of A(H) or phi(u) = phi(v), and all the fibers phi(-1)(v), for v is an element of 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.