In 1980, Burr conjectured that every directed graph with chromatic number $2k-2$ contains any oriented tree of order $k$ as a subdigraph. Burr showed that chromatic number $(k-1)^2$ suffices, which was improved in 2013 to $\frac{ k^2}{ 2} - \frac{ k}{ 2} + 1$ by Addario-Berry et al. We give the first subquadratic bound for Burr's conjecture, by showing that every directed graph with chromatic number $8\sqrt{ \frac{ 2}{ 15}} k \sqrt{ k} + O(k)$ contains any oriented tree of order $k$. Moreover, we provide improved bounds of $\sqrt{ \frac{ 4}{ 3}} k \sqrt{ k}+O(k)$ for arborescences, and $(b-1)(k-3)+3$ for paths on $b$ blocks, with $b\ge 2$.
Categories: math.CO cs.DM