Majority Colourings of Digraphs

Stephan Kreutzer, Sang-il Oum, Paul Seymour, Dominic van der Zypen, David R. Wood

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.

Keywords


Graph theory; Digraphs; Graph colouring; Majority Colouring

Full Text: PDF