Uniquely D-colourable Digraphs with Large Girth

Harutyunyan, Ararat ; Kayll, P. Mark ; Mohar, Bojan ; Rafferty, Liam

Canadian journal of mathematics, Tome 64 (2012) no. 6, pp. 1310-1328

Résumé

Let $C$ and $D$ be digraphs. A mapping $f:V\left( D \right)\to V\left( C \right)$ is a $C$ -colouring if for every arc $uv$ of $D$ , either $f\left( u \right)f\left( v \right)$ is an arc of $C$ or $f\left( u \right)=f\left( v \right)$ , 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\ge 1$ , there are uniquely circularly $r$ -colourable digraphs with arbitrarily large girth.

Détail

DOI : 10.4153/CJM-2011-084-9

Mots-clés : 05C15, 05C20, 60C05, digraph colouring, acyclic homomorphism, circular chromatic number, girth