Majority choosability of digraphs (Q2409821): Difference between revisions

Summary: A \textit{majority coloring} of a digraph is a coloring of its vertices such that for each vertex \(v\), at most half of the out-neighbors of \(v\) have the same color as \(v\). A digraph \(D\) is \textit{majority \(k\)-choosable} if for any assignment of lists of colors of size \(k\) to the vertices there is a majority coloring of \(D\) from these lists. We prove that every digraph is majority \(4\)-choosable. This gives a positive answer to a question posed recently by \textit{S. Kreutzer} et al. [ibid. 24, No. 2, Research Paper P2.25, 9 p. (2017; Zbl 1364.05029)]. We obtain this result as a consequence of a more general theorem, in which majority condition is profitably extended. For instance, the theorem implies also that every digraph has a coloring from arbitrary lists of size three, in which at most \(2/3\) of the out-neighbors of any vertex share its color. This solves another problem posed by the same authors, and supports an intriguing conjecture stating that every digraph is majority \(3\)-colorable.