Title: Out-colourings of Digraphs,
Abstract: We study vertex colourings of digraphs so that no out-neighbourhood is
monochromatic and call such a colouring an {\bf out-colouring}. The problem of
deciding whether a given digraph has an out-colouring with only two colours
(called a 2-out-colouring) is ${\cal
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 3 has a 2-out-colouring.
Furthermore, we show that every semicomplete digraph on at least 7 vertices has
a 2-out-colouring if and only if it has a {\bf 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\geq 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
$2k+c\sqrt{k}$ has such a partition. This is tight up to the value of $c$.