id: 06111141
dt: j
an: 06111141
au: Harutyunyan, Ararat; Kayll, P.Mark; Mohar, Bojan; Rafferty, Liam
ti: Uniquely $D$-colourable digraphs with large girth.
so: Can. J. Math. 64, No. 6, 1310-1328 (2012).
py: 2012
pu: University of Toronto Press, Toronto
la: EN
cc: 
ut: $C$-colouring; uniquely circularly $r$-colourable digraphs
ci: 
li: doi:10.4153/CJM-2011-084-9
ab: Summary: Let $C$ and $D$ be digraphs. A mapping $f\colon V(D)\to V(C)$ is a
    $C$-colouring if for every arc $uv$ of $D$, either $f(u)f(v)$ is an arc
    of $C$ or $f(u)=f(v)$, and the preimage of every vertex of $C$ induces
    an acyclic subdigraph in $D$. We say that $D$ is $C$-colourable if it
    admits a $C$-colouring and that $D$ is uniquely $C$-colourable if it is
    surjectively $C$-colourable and any two $C$-colourings of $D$ differ by
    an automorphism of $C$. We prove that if a digraph $D$ is not
    $C$-colourable, then there exist digraphs of arbitrarily large girth
    that are $D$-colourable but not $C$-colourable. Moreover, for every
    digraph $D$ that is uniquely $D$-colourable, there exists a uniquely
    $D$-colourable digraph of arbitrarily large girth. In particular, this
    implies that for every rational number $r\geq 1$, there are uniquely
    circularly $r$-colourable digraphs with arbitrarily large girth.
rv: