{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:44:15Z","timestamp":1753893855296,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>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 $\\varphi: V(D) \\rightarrow V(H)$ such that $uv \\in A(D)$ implies that either $\\varphi(u)\\varphi(v) \\in A(H)$ or $\\varphi(u)=\\varphi(v)$, and all the `fibers' $\\varphi^{-1}(v)$, for $v \\in V(H)$, of $\\varphi$ are acyclic. In this language, a core is a digraph $D$ for which there does not exist an acyclic homomorphism \u00a0from $D$ to a proper subdigraph of itself. Here we prove some basic results about digraph cores and construct highly chromatic cores without short cycles.<\/jats:p>","DOI":"10.37236\/4823","type":"journal-article","created":{"date-parts":[[2020,1,10]],"date-time":"2020-01-10T15:58:33Z","timestamp":1578671913000},"source":"Crossref","is-referenced-by-count":0,"title":["A Construction of Uniquely $n$-Colorable Digraphs with Arbitrarily Large Digirth"],"prefix":"10.37236","volume":"24","author":[{"given":"Michael","family":"Severino","sequence":"first","affiliation":[]}],"member":"23455","published-online":{"date-parts":[[2017,4,13]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v24i2p1\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v24i2p1\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,17]],"date-time":"2020-01-17T05:02:43Z","timestamp":1579237363000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v24i2p1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4,13]]},"references-count":0,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2017,4,13]]}},"URL":"https:\/\/doi.org\/10.37236\/4823","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2017,4,13]]},"article-number":"P2.1"}}