Acyclic subgraph chromatic number in tournaments

Conjecture 4.1 · arXiv:1912.07722

arXiv Conjecture high confidence— first stated 2024-05-30

Authors: Jacob Fox, Matthew Kwan, Benny Sudakov

Status open high confidence

The conjecture that every n-vertex tournament has an acyclic subgraph with chromatic number at least n^{3/4-o(1)} (equivalently g(k) ≤ k^{4/3+o(1)}) remains open. The source paper itself establishes the bounds n^{5/9-o(1)} ≤ f(G) ≤ n^{3/4+o(1)}, leaving a gap between the proven lower bound and the conjectured tight value. A 2025 follow-up by Yuster extends the n^{5/9-o(1)} lower bound to digraphs with small bipartite independence number but does not improve the tournament lower bound or resolve the conjecture.

Cited literature (1)

partial Acyclic subgraphs of digraphs with high chromatic number (2025)

Raphael Yuster · European Journal of Combinatorics · arXiv:2512.21950

Generalises the n^{5/9-o(1)} lower bound of Fox–Kwan–Sudakov from tournaments to digraphs satisfying f(G) ≥ n^{5/9-o(1)} s^{-14/9} where s is the bipartite independence number, but does not improve the lower bound for tournaments and leaves Conjecture 4.1 open.

Reviewer notes. The paper itself already establishes the matching upper bound n^{3/4+o(1)} via a randomised projective-plane construction, so the conjecture would pin down the correct exponent as 3/4. As of May 2026, the best proven lower bound for tournaments remains n^{5/9-o(1)} from the source paper; no follow-up has closed the gap to n^{3/4-o(1)}.

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

Conjecture. Every $n$-vertex tournament has an acyclic subgraph with chromatic number at least $n^{3/4-o\mathopen{}\mathclose{{}\left(1}\right)}$. That is, $g\mathopen{}\mathclose{{}\left(k}\right)\leq k^{4/3+o\mathopen{}\mathclose{{}\left(1}\right)}$.

Context

Having established $k^{4/3-o(1)}\leq g(k)\leq k^{9/5+o(1)}$, the authors suspect the lower bound is closer to the truth and propose this conjecture. The lower bound is achieved via a randomized projective-plane construction, and the authors also wonder whether a simpler explicit construction on $n=q^{2}$ vertices attains the same bound.

Source paper

Acyclic subgraphs of tournaments with high chromatic number
Jacob Fox, Matthew Kwan, Benny Sudakov · 2024-05-30
https://arxiv.org/abs/1912.07722