Linear bound for majority colourings of digraphs (Q1671650)

Summary: Given \(\eta \in [0, 1]\), a colouring \(C\) of \(V(G)\) is an \textit{\(\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 \textit{M. Anholcer} et al. [ibid. 24, No. 3, Research Paper P3.57, 5 p. (2017; Zbl 1375.05079)], who proved the cases \(k=3\) and \(k=4\) and claim a weaker result for general \(k\).