Let $C$ and $D$ be digraphs. A mapping $fcolon V(D) o 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 $rgeq 1$, there are uniquely circularly $r$-colourable digraphs with arbitrarily large girth.
展开▼
机译：令$ C $和$ D $为有向图。如果对于$ D $的每个弧$ uv $，$ f（u）f（v）$都是$ C的弧，则映射$ fcolon V（D）o V（C）$就是$ C $着色。 $或$ f（u）= f（v）$，并且$ C $的每个顶点的原像会在$ D $中引入一个无环子图。我们说，如果$ D $接受$ C $着色，那么$ D $是$ C $着色;如果说是$ C $着色，并且任意两个$ C $着色，则$ D $是唯一$ C $着色。 $ D $的不同之处在于$ C $的同构性。我们证明如果图$ D $不是$ C $可着色的，则存在任意大周长的图是$ D $可着色的，而不是$ C $可着色的。此外，对于每一个独特的$ D $着色的有价$ D $，都有一个独特的$ D $着色的任意大周长的有向图。特别是，这意味着对于每个有理数$ rgeq 1 $，都有唯一的圆形$ r $着色图，其周长任意大。
展开▼
