A Study of $k$-dipath Colourings of Oriented Graphs

We examine $t$-colourings of oriented graphs in which, for a fixed integer $k\geq 1$, vertices joined by a directed path of length at most $k$ must beassigned different colours. A homomorphism model that extends the ideas ofSherk for the case $k=2$ is described. Dichotomy theorems for the complexity ofthe problem of deciding, for fixed $k$ and $t$, whether there exists such a$t$-colouring are proved.Comment: 14 page