Majority Colourings of Digraphs

  • Stephan Kreutzer
  • Sang-il Oum
  • Paul Seymour
  • Dominic van der Zypen
  • David R. Wood
DOI: https://doi.org/10.37236/6410
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
How to Cite
Kreutzer, S., Oum, S.- il, Seymour, P., van der Zypen, D., & Wood, D. R. (2017). Majority Colourings of Digraphs. The Electronic Journal of Combinatorics, 24(2), P2.25. https://doi.org/10.37236/6410
Issue
Volume 24, Issue 2 (2017)
Article Number
P2.25