Acyclic high-chromatic subgraph existence in tournaments
Problem 1.1 · arXiv:1912.07722
Status open high confidence
Problem 1.1 asks for the exact growth rate of f(k), the minimum chromatic number of an oriented graph that guarantees an acyclic k-chromatic subgraph. The best known upper bound remains f(k) ≤ k² - 2k + 2 and the best known lower bound is f(k) ≥ 1 + ⌊√(k-1)⌋, leaving a large gap. The closely related arXiv:2512.21950 (Yuster, 2025) extends the Fox-Kwan-Sudakov tournament result to general digraphs with bounded bipartite independence number but does not address the f(k) question for oriented graphs. No resolution of Problem 1.1 was found in the indexed literature.
Reviewer notes. No paper resolving Problem 1.1 was found. The related arXiv:2512.21950 (Yuster, 2025, published in European Journal of Combinatorics) extends Fox-Kwan-Sudakov's tournament result to general digraphs with bounded bipartite independence number and mentions f(k) in passing (noting f(k) ≥ 1+⌊√(k-1)⌋), but its main contribution is the vertex-count setting, not the chromatic-number formulation of Problem 1.1. The upper bound f(k) ≤ k²-2k+2 from the source paper appears to remain the best known.
Context
Addario-Berry, Havet, Sales, Reed, and Thomassé observed that if a $k$-chromatic oriented graph has no directed cycle it contains every oriented tree of order $k$, and suggested that proving acyclic subgraphs of high chromatic number exist in $k$-chromatic oriented graphs could yield improved bounds towards Burr's conjecture. The trivial two-part partition gives $f(k)\leq k^{2}$, subsequently refined to $f(k)\leq k^{2}-2k+2$, but substantially improving this bound seems to require new ideas.
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