Oriented trees in $O(k \sqrtk)$-chromatic digraphs, a subquadratic bound for Burr's conjecture
<|reference_start|>Oriented trees in $O(k \sqrtk)$-chromatic digraphs, a subquadratic bound for Burr's conjecture: 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$.<|reference_end|>
@article{bessy2024oriented,
    title={Oriented trees in $O(k \sqrt{k})$-chromatic digraphs, a subquadratic
  bound for Burr's conjecture},
    author={St'ephane Bessy, Daniel Gonc{c}alves, Amadeus Reinald},
    journal={arXiv preprint arXiv:2402.19351},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.19351},
    primaryClass={math.CO cs.DM}
}