Open Problem Garden

The value would be best possible, since the oriented tree consisting of a vertex dominating other vertices is not contained in any digraph in which every vertex has outdegree . The condition on the trees be antidirected cannot be suppressed. In a bipartite digraph with bipartition such that all arcs are directed from to , all the trees contained in are antidirected.

This conjecture for symmetric digraphs is equivalent to the celebrated Erdös-Sos conjecture for undirected graphs. (see [E]).

Conjecture   Let be a graph. If , then contains every tree of order .

Addario-Berry et al. Conjecture also implies Burr's conjecture (see Oriented trees in n-chromatic digraphs) for antidirected trees, since every digraph with chromatic number contains a colour-critical digraph has minimum degree at least , and so whose number of vertices is at least , which exceeds .

This conjecture has only been proved [AHL+] for antidirected trees of diameter at most .