Majority Colourings of Digraphs

Stephan Kreutzer, Sang-il Oum, Paul Seymour +2

We prove that every digraph has a vertex 4-colouring such that for each vertex $v$, at most half the out-neighbours of $v$ receive the same colour as $v$. We then obtain several re…