Sublinear majority 3-coloring of digraphs

Open Problem 1 · 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 1 asks whether a universal constant β < 1 exists such that every digraph admits a 3-colouring where at most β·deg⁺(v) out-neighbours of each vertex v share its colour. Knox and Šámal (EJC 2018) resolve this affirmatively with β = 2/3: they prove that for any list assignment of size k, every digraph has a 2/k-majority list-colouring; specialising to k = 3 with all lists identical gives an ordinary 3-colouring with β = 2/3 < 1. The stronger majority 3-colouring conjecture (β = 1/2) remains open; Anastos, Lamaison, Steiner, and Szabó (2019) established it for digraphs with chromatic number ≤ 6 or dichromatic number ≤ 3, and for digraphs with maximum out-degree ≤ 4.

Cited literature (2)

proof Linear Bound for Majority Colourings of Digraphs (2018)

Fiachra Knox, Robert Šámal · The Electronic Journal of Combinatorics

Proves that every digraph with list assignments of size k has a 2/k-majority list-colouring (best possible for even k); setting k = 3 and all lists equal to {1,2,3} resolves Open Problem 1 with the universal constant β = 2/3 < 1.
partial Majority Colorings of Sparse Digraphs (2019)

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

Proves the stronger majority (β = 1/2) 3-choosability conjecture for digraphs with chromatic number ≤ 6 or dichromatic number ≤ 3, and for max out-degree ≤ 4 or max degree ≤ 7; shows every digraph has a fractional majority 3.9602-colouring; establishes NP-completeness of majority 2-colourability.

Reviewer notes. Open Problem 1 is resolved by Knox and Šámal (EJC 2018, v25i3p29) with β = 2/3, since their list-colouring result specialises to ordinary 3-colourings. The stronger majority 3-colouring conjecture (β = 1/2) remains open as of 2026. The five internal references all point to the same paper (arXiv:1911.01954), which targets the harder β = 1/2 conjecture for sparse digraphs.

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

Problem. Is there a constant $\beta < 1$ for which every digraph has a 3-colouring such that for every vertex $v$, at most $\beta \deg^+(v)$ out-neighbours receive the same colour as $v$?

Context

Theorems 3 and 4 establish majority 3-colourings (i.e., $\beta = \frac{1}{2}$) under extra degree assumptions (logarithmic minimum outdegree, or bounded minimum/maximum degree ratio). Whether any $\beta < 1$ holds universally for 3-colourings without degree conditions is open.

Notes. PDF source

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