Linear Bound for Majority Colourings of Digraphs

Abstract

Given $\eta \in [0,1]$, a colouring $C$ of $V(G)$ is an $\eta$-majority colouring if at most $\eta d^{+}(v)$ out-neighbours of $v$ have colour $C(v)$, for any $v\in V(G)$. We show that every digraph $G$ equipped with an assignment of lists $L$, each of size at least $k$, has a $2/k$-majority $L$-colouring. For even $k$ this is best possible, while for odd $k$ the constant $2/k$ cannot be replaced by any number less than $2/(k+1)$. This generalizes a result of Anholcer, Bosek and Grytczuk, who proved the cases $k=3$ and $k=4$ and gave a weaker result for general $k$.

3 pages