Majority 3-coloring of Eulerian digraphs

Status open high confidence

Open Problem 3 — whether every Eulerian digraph has a majority 3-colouring — remains unresolved as of May 2026. The source paper already establishes that Eulerian digraphs admit a 3-colouring in which each vertex v has at most (2/3)deg(v) same-colour in-or-out-neighbours, but the stricter majority bound of (1/2)deg^+(v) same-colour out-neighbours is still open. Anastos, Lamaison, Steiner and Szabó (2019, arXiv:1911.01954) made substantial progress on the broader Open Problem 1 (majority 3-coloring for all digraphs), proving partial cases for sparse digraphs, but their results do not directly resolve the Eulerian case. No subsequent paper found in the literature settles Open Problem 3.

Cited literature (1)

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

  Proves the broader majority 3-coloring conjecture (Open Problem 1) for digraphs with chromatic number at most 6 or dichromatic number at most 3, and proves majority 3-choosability for digraphs with max out-degree at most 4 or max degree at most 7; does not specifically address Eulerian digraphs (Open Problem 3).

Reviewer notes. All six internal-reference entries reduce to a single paper (arXiv:1911.01954). Open Problem 3 is strictly about Eulerian digraphs and is a weaker conjecture than Open Problem 1; no paper found that exploits the Eulerian structure to achieve a full majority 3-colouring. The conjecture is open with high confidence.

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