A near-linear upper bound for Burr's conjecture

Abstract

Let $f(k)$ denote the smallest integer such that every oriented graph $D$ with chromatic number at least $f(k)$ contains every oriented tree on $k$ vertices. Burr (1980) showed that $f(k)\le (k-1)^2$ and conjectured that $f(k)=2k-2$. Bessy, Gon\c{c}alves and Reinald (2025) proved that $f(k)=O(k^{3/2})$. In this paper, by using an absorbing set method, we show that $f(k)\le \lfloor 31\log (k!)\rfloor=O(k\log k)$.