Majority 1/k out-neighbour colouring digraphs

Conjecture 9 · arXiv:1608.03040

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

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

Status disproved medium confidence

Conjecture 9 from arXiv:1608.03040 asserts that for k≥2, every digraph can be (k+1)-coloured so that each vertex shares its colour with at most 1/k of its out-neighbours (i.e. the generalised majority chromatic number m(k) equals k+1). Girão, Kittipassorn, and Popielarz (arXiv:1701.03780, CPC 2017) proved that m(k) ∈ {2k−1, 2k}, establishing in particular a lower bound m(k) ≥ 2k−1; for k≥3 this exceeds k+1, disproving the conjecture for those values of k. The special case k=2 (the majority 3-colouring conjecture) remains open; Anastos, Lamaison, Steiner, and Szabó (arXiv:1911.01954, 2019) proved it for digraphs with chromatic number at most 6 or dichromatic number at most 3, and established NP-completeness of majority 2-colourability.

Cited literature (2)

counterexample Generalised Majority Colourings of Digraphs (2017)

António Girão, Teeradej Kittipassorn, Kamil Popielarz · Combinatorics, Probability and Computing, Volume 26, Issue 6, pp. 850-855 · arXiv:1701.03780

Proves m(k) ∈ {2k−1, 2k}, where m(k) is the minimum number of colours guaranteeing each vertex shares its colour with at most 1/k of its out-neighbours; the lower bound m(k) ≥ 2k−1 > k+1 for k≥3 disproves Conjecture 9 for all such k.
partial Majority Colorings of Sparse Digraphs (2019)

Michael Anastos, Ander Lamaison, Raphael Steiner, Tibor Szabó · Electronic Journal of Combinatorics, vol. 28 no. 2 · arXiv:1911.01954

Proves the k=2 case (majority 3-colouring) for digraphs with chromatic number ≤6 or dichromatic number ≤3; shows majority 2-colourability is NP-complete; obtains fractional bound m(2) ≤ 3.9602 via probabilistic methods.

Reviewer notes. Conjecture 9 is disproved for k≥3 by arXiv:1701.03780 (Girão, Kittipassorn, Popielarz, CPC 2017), which establishes m(k)≥2k−1>k+1 for those k. The surviving open case is k=2, i.e. the majority 3-colouring conjecture (Conjecture 2 of the same source paper). Confidence is medium because the full counterexample construction in 1701.03780 was not read directly, only the Cambridge Core abstract and arXiv abstract page.

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

Conjecture. For $k \geq 2$, every digraph has a vertex $(k+1)$-colouring such that for each vertex $v$, at most $\frac{1}{k}\deg^+(v)$ out-neighbours of $v$ receive the same colour as $v$.

Context

This is the natural generalisation of Conjecture 2 to arbitrary $k$. The proof of Theorem 1 generalises to give an upper bound of $k^2$ colours; whether $O(k)$ colours suffice is explicitly stated as open. The conjecture is best possible, as shown by the $k$-th power of a directed $n$-cycle with $n \not\equiv 0 \pmod{k+1}$.

Also stated in

Majority Colourings of Digraphs (2016-08-10)

Notes. PDF source — '$k > 2$' in extracted text likely renders '$k \geq 2$'; LaTeX corrected to $k \geq 2$ for mathematical consistency with the stated generalisation of Conjecture 2.

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