Out‐colourings of digraphs

We study vertex colourings of digraphs so that no out‐neighbourhood is monochromatic and call such a colouring an out‐colouring. The problem of deciding whether a given digraph has an out‐colouring with only two colours (called a 2‐out‐colouring) is NP ‐complete. We show that for every choice of positive integers r , k there exists a k ‐strong bipartite tournament, which needs at least r colours in every out‐colouring. Our main results are on tournaments and semicomplete digraphs. We prove that, except for the Paley tournament P 7 , every strong semicomplete digraph of minimum out‐degree at least three has a 2‐out‐colouring. Furthermore, we show that every semicomplete digraph on at least seven vertices has a 2‐out‐colouring if and only if it has a balanced such colouring, that is, the difference between the number of vertices that receive colour 1 and colour 2 is at most one. In the second half of the paper, we consider the generalization of 2‐out‐colourings to vertex partitions ( V 1 , V 2 ) of a digraph D so that each of the three digraphs induced by respectively, the vertices of V 1 , the vertices of V 2 and all arcs between V 1 and V 2 , have minimum out‐degree k for a prescribed integer k ≥ 1 . Using probabilistic arguments, we prove that there exists an absolute positive constant c so that every semicomplete digraph of minimum out‐degree at least 2 k + c k has such a partition. This is tight up to the value of c .