Generalised Majority Colourings of Digraphs

Abstract

The purpose of this note is to draw attention to problems related to a concept called majority colouring recently studied by Kreutzer, Oum, Seymour, van der Zypen and Wood. They raised a problem of determining, for a natural number $k$, the smallest number $m=m(k)$ such that every digraph can be coloured with $m$ colours where each vertex has the same colour as at most $1/k$ proportion of its out-neighbours. We show that $m(k)\in \{2k-1,2k\}$. We also prove a result supporting the conjecture that $m(2)=3$. Moreover, we prove similar results for a more general concept called majority choosability.

4 pages

References in corpus (1)

• Majority Colourings of Digraphs

Cited by in corpus (2)

• A note on digraph splitting
• Mrs. Correct and Majority Colorings