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 claim a weaker result for general $k$.
@article{10_37236_6762,
author = {Fiachra Knox and Robert \v{S}\'amal},
title = {Linear bound for majority colourings of digraphs},
journal = {The electronic journal of combinatorics},
year = {2018},
volume = {25},
number = {3},
doi = {10.37236/6762},
zbl = {1395.05070},
url = {http://geodesic.mathdoc.fr/articles/10.37236/6762/}
}
TY - JOUR
AU - Fiachra Knox
AU - Robert Šámal
TI - Linear bound for majority colourings of digraphs
JO - The electronic journal of combinatorics
PY - 2018
VL - 25
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/6762/
DO - 10.37236/6762
ID - 10_37236_6762
ER -
%0 Journal Article
%A Fiachra Knox
%A Robert Šámal
%T Linear bound for majority colourings of digraphs
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/6762/
%R 10.37236/6762
%F 10_37236_6762
Fiachra Knox; Robert Šámal. Linear bound for majority colourings of digraphs. The electronic journal of combinatorics, Tome 25 (2018) no. 3. doi: 10.37236/6762
