Uniquely $D$-colourable Digraphs with Large Girth

http://dx.doi.org/10.4153/CJM-2011-084-9
Canad. J. Math. 64(2012), 1310-1328

  Published:2011-12-06
 Printed: Dec 2012

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.