Majority choosability constant for digraphs

Open Problem 7 · arXiv:1608.03040

arXiv Problem high confidence— first stated 2016-08-10

Authors: Stephan Kreutzer, Sang-il Oum, Paul Seymour, Dominic van der Zypen, David R. Wood

Status solved high confidence

Open Problem 7 (whether every digraph is majority $c$-choosable for some constant $c$) was answered affirmatively by Anholcer, Bosek, and Grytczuk (EJC 2017), who proved that every digraph is majority 4-choosable, establishing $c=4$ as a valid universal constant. Subsequently, Anastos, Lamaison, Steiner, and Szabó (2019) proved majority 3-choosability for sparse classes (list chromatic number at most 6, dichromatic number at most 3, or max out-degree at most 4) and showed that deciding majority 2-colorability is NP-complete; whether $c=3$ suffices for all digraphs remains open.

Cited literature (2)

proof Majority Choosability of Digraphs (2017)

Marcin Anholcer, Bartłomiej Bosek, Jarosław Grytczuk · The Electronic Journal of Combinatorics · arXiv:1608.06912

Proves that every digraph is majority 4-choosable, giving a positive answer to Open Problem 7 with universal constant c=4.
partial Majority Colorings of Sparse Digraphs (2019)

Michael Anastos, Ander Lamaison, Raphael Steiner, Tibor Szabó · arXiv preprint · arXiv:1911.01954

Proves majority 3-choosability for digraphs with list chromatic number at most 6 or dichromatic number at most 3, and shows that deciding majority 2-colorability is NP-complete.

Reviewer notes. Open Problem 7 is settled positively: every digraph is majority 4-choosable (c=4), proved by Anholcer-Bosek-Grytczuk whose arXiv preprint (1608.06912) appeared shortly after the source paper in the same month (August 2016) and was published in EJC in 2017. The EJC URL https://www.combinatorics.org/v24i3p57 was verified with WebFetch. The arXiv ID 1608.06912 is inferred from the NASA/ADS abstract identifier 2016arXiv160806912A and was not directly WebFetch-verified. The residual open question is whether c=3 suffices for all digraphs.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Problem. A digraph $G$ is majority $c$-choosable if for every function $L : V(G) \to \mathcal{Z}$ with $|L(v)| \geq c$ for each vertex $v \in V(G)$, there is a majority colouring of $G$ with each vertex $v$ coloured from $L(v)$. Is every digraph majority $c$-choosable for some constant $c$?

Context

Acyclic digraphs are shown to be majority 2-choosable (from the proof of Theorem 1), and Theorems 3 and 4 extend to the choosability setting; whether a universal constant $c$ covers all digraphs is open.

Notes. PDF source — $\mathcal{Z}$ likely denotes the integers $\mathbb{Z}$ (list assignment).

Source paper

Majority Colourings of Digraphs
Stephan Kreutzer, Sang-il Oum, Paul Seymour, Dominic van der Zypen, David R. Wood · 2016-08-10
https://arxiv.org/abs/1608.03040 PDF source