文摘
We develop the theory of oriented colourings which are injective on in-neighbourhoods. The complexity of deciding if the minimum number of colours is at most the fixed integer k is determined, as is Brooks-Theorem type bound. The latter relies, in part, on a characterization of the oriented graphs in which each vertex must be assigned a different colour. A better, tight bound is determined for oriented trees, and a linear algorithm that decides if a given tree can be coloured with at most k colours, where k is fixed, is described.