Majority colourings of digraphs

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

Research output: Contribution to journalArticleResearchpeer-review

14 Citations (Scopus)


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
Article number#P2.25
Number of pages9
JournalElectronic Journal of Combinatorics
Issue number2
Publication statusPublished - 19 May 2017

Cite this