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.

Author Biography

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