Majority Colourings of Digraphs

作者：Kreutzer Stephan^*; Oum Sang il; Seymour Paul; van der Zypen Dominic; Wood David R

来源：ELECTRONIC JOURNAL OF COMBINATORICS, 2017, 24(2): P2.25.

DOI：10.37236/6410

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.

• 出版日期2017-5-19