# Majority Colourings of Digraphs

• Stephan Kreutzer
• Sang-il Oum
• Paul Seymour
• Dominic van der Zypen
• David R. Wood
Keywords: Graph theory, Digraphs, Graph colouring, Majority Colouring

### Abstract

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 results related to the conjecture obtained by replacing 4 by 3.

Stephan Kreutzer
TU Berlin
Published
2017-05-19
Article Number
P2.25