Majority 3-coloring of digraphs

Conjecture 2 · 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 partial high confidence

The conjecture that every digraph has a majority 3-colouring remains open in full generality as of 2026. Anastos, Lamaison, Steiner, and Szabó (arXiv:1911.01954, EJC 2021) proved it for digraphs with chromatic number at most 6 or dichromatic number at most 3 (covering all planar digraphs), and proved the stronger majority 3-choosability for digraphs with maximum out-degree at most 4 or maximum degree at most 7. Their probabilistic argument achieves a fractional bound of K ≤ 3.9602, approaching but not reaching the conjectured value of 3. A 2025 paper in Acta Mathematicae Applicatae Sinica reports further new partial results, and the conjecture is still described as 'far from being resolved' in recent literature.

Cited literature (1)

partial Majority Colorings of Sparse Digraphs (2021)

Michael Anastos, Ander Lamaison, Raphael Steiner, Tibor Szabó · Electronic Journal of Combinatorics · arXiv:1911.01954

Proves the conjecture for digraphs with chromatic number at most 6 or dichromatic number at most 3, and proves the stronger majority 3-choosability for digraphs with maximum out-degree at most 4 or maximum degree at most 7; also establishes a fractional majority coloring bound of K ≤ 3.9602.

Reviewer notes. Conjecture confirmed open as of 2025 by multiple sources. Additional unverified leads found within cap: Haselgrave (2020) 'Countable graphs are majority 3-choosable' (Warwick eprint 144155, PDF timed out); Acta Mathematicae Applicatae Sinica 2025 paper (doi:10.1007/s10255-025-0002-0) reporting new partial results (Springer auth-wall, not fetched); an IJMTT paper showing every digraph D with minimum out-degree ≥ 28·ln|D| has a majority 3-colouring (arxiv ID not found). These could not be verified within the 5-call cap.

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

Conjecture. Every digraph has a majority 3-colouring.

Context

This conjecture naturally arises from Theorem 1, which shows every digraph has a majority 4-colouring. It would be best possible: odd directed cycles require 3 colours (since each vertex has outdegree 1, a majority colouring is a proper colouring), and circulant digraphs with large odd outdegree also witness this lower bound.

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