A theory of 2-dipath colourings.
Gary MacGillivray, Kailyn M. Sherk · Australas. J Comb. · 2014
We study colourings of oriented graphs in which vertices joined by a directed path of length two are assigned different colours. There are two models, depending on whether adjacent vertices must also be assigned different colours. In each case we describe a homomorphism model, a dichotomy theorem for the complexity of the problem of deciding whether there exists such a colouring with a fixed number of colours, and a polynomial time algorithm for determining the minimum number of colours needed to colour a given multipartite tournament.