Majority colourings of digraphs

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

Research output: Contribution to journalArticle

6 Scopus citations


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.

Original languageEnglish (US)
Article number#P2.25
JournalElectronic Journal of Combinatorics
Issue number2
StatePublished - May 19 2017

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Majority colourings of digraphs'. Together they form a unique fingerprint.

  • Cite this

    Kreutzer, S., Oum, S. I., Seymour, P., van der Zypen, D., & Wood, D. R. (2017). Majority colourings of digraphs. Electronic Journal of Combinatorics, 24(2), [#P2.25].