# Antidirected trees in digraphs

 Importance: Medium ✭✭
 Author(s): Addario-Berry, Louigi Havet, Frédéric Linhares Sales, Claudia Reed, Bruce A. Thomassé, Stéphan
 Subject: Graph Theory » Directed Graphs
 Keywords:
 Posted by: fhavet on: February 26th, 2013

An antidirected tree is an orientation of a tree in which every vertex has either indegree 0 or outdergree 0.

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

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 .

## Bibliography

*[AHL+] L. Addario-Berry, F. Havet, C. Linhares Sales, B. Reed, and S. Thomassé. Oriented trees in digraphs. Discrete Mathematics, 313(8):967-974, 2013.

[E] P. Erdös, Some problems in graph theory, Theory of Graphs and Its Applications, M. Fielder, Editor, Academic Press, New York, 1965, pp. 29--36.

* indicates original appearance(s) of problem.