Abstract view

# Uniquely $D$-colourable Digraphs with Large Girth

Published:2011-12-06
Printed: Dec 2012
• Ararat Harutyunyan,
Department of Mathematics, Simon Fraser University, Burnaby, B.C. V5A 1S6
• P. Mark Kayll,
Department of Mathematical Sciences, University of Montana, Missoula MT 59812-0864, USA
• Bojan Mohar,
Department of Mathematics, Simon Fraser University, Burnaby, B.C. V5A 1S6
• Liam Rafferty,
Department of Mathematical Sciences, University of Montana, Missoula MT 59812-0864, USA
Features coming soon:
Citations   (via CrossRef) Tools: Search Google Scholar:
 Format: LaTeX MathJax PDF

## Abstract

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.