Majority colourings of digraphs

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

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

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.

Original languageEnglish (US)
Article number#P2.25
JournalElectronic Journal of Combinatorics
Volume24
Issue number2
DOIs
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