Majority 3-coloring of tournaments

Status open high confidence

The question of whether every tournament admits a majority 3-colouring remains open as of May 2026. Anastos, Lamaison, Steiner, and Szabó (2019) proved the broader majority 3-coloring conjecture for digraphs with chromatic number at most 6 or dichromatic number at most 3, and majority 3-choosability for digraphs with maximum out-degree at most 4 or maximum degree at most 7, covering some but not all tournaments. Multiple recent surveys confirm the general majority 3-coloring conjecture for digraphs is 'far from being resolved', and no complete resolution for tournaments has been found.

Cited literature (1)

• partial Majority Colorings of Sparse Digraphs (2019)
  Michael Anastos, Ander Lamaison, Raphael Steiner, Tibor Szabó · The Electronic Journal of Combinatorics · arXiv:1911.01954

  Proves the majority 3-coloring conjecture for digraphs with chromatic number at most 6 or dichromatic number at most 3 (covering some tournaments) and majority 3-choosability for digraphs with maximum out-degree at most 4 or maximum degree at most 7; the general tournament case remains open.

Reviewer notes. All five internal reference records de-duplicate to arXiv:1911.01954. The fuzz=98 record's attribution of 'answering the question negatively' is misleading for this specific open problem: Theorem 9 of that paper establishes NP-completeness of deciding majority 2-colorability for general digraphs, which is unrelated to Open Problem 2 (3-colorability of tournaments). Web search results from 2025 confirm the general majority 3-coloring conjecture is described as far from resolved. No paper specifically resolving the tournament case was found.

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