Oriented trees in digraphs

Let f(k)f(k) be the smallest integer such that every f(k)f(k)-chromatic digraph contains every oriented tree of order kk. Burr proved f(k)≤(k−1)2f(k)≤(k−1)2 in general, and he conjectured f(k)=2k−2f(k)=2k−2. Burr also proved that every (8k−7)(8k−7)-chromatic digraph contains every antidirected tree. We improve both of Burr’s bounds. We show that f(k)≤k2/2−k/2+1f(k)≤k2/2−k/2+1 and that every antidirected tree of order kk is contained in every (5k−9)(5k−9)-chromatic digraph.We make a conjecture that explains why antidirected trees are easier to handle. It states that if |E(D)|>(k−2)|V(D)||E(D)|>(k−2)|V(D)|, then the digraph DD contains every antidirected tree of order kk. This is a common strengthening of both Burr’s conjecture for antidirected trees and the celebrated Erdős-Sós Conjecture. The analogue of our conjecture for general trees is false, no matter what function f(k)f(k) is used in place of k−2k−2. We prove our conjecture for antidirected trees of diameter 3 and present some other evidence for it.Along the way, we show that every acyclic kk-chromatic digraph contains every oriented tree of order kk and suggest a number of approaches for making further progress on Burr’s conjecture.