Louigi Addario-Berry
email: louigi@math.mcgill.ca.

Frédéric Havet
email: fhavet@sophia.inria.fr.

Cláudia Linhares Sales

Bruce Reed
email: breed@cs.mcgill.ca.

Stéphan Thomassé
email: stephan.thomasse@ens-lyon.fr.

Oriented trees in digraphs

Let f (k) be the smallest integer such that every f (k)-chromatic digraph contains every oriented tree of order k. Burr proved f (k) ≤ (k -1) 2 in general, and he conjectured f (k) = 2k -2. Burr also proved that every (8k -7)-chromatic digraph contains every antidirected tree. We improve both of Burr's bounds. We show that f (k) ≤ k 2 /2 -k/2 + 1 and that every antidirected tree of order k is contained in every (5k -9)-chromatic digraph.

We make a conjecture that explains why antidirected trees are easier to handle. It states that if

then the digraph D contains every antidirected tree of order k. 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) is used in place of k -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 k-chromatic digraph contains every oriented tree of order k and suggest a number of approaches for making further progress on Burr's conjecture.

Introduction

We assume the reader is familar with the basic concepts in graph theory; we follow the notation in [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF] and suggest readers who need a refresher consult that book.

All the graphs and digraphs we will consider here are simple, i.e. they have no loops nor multiple arcs. An orientation of a graph G is a digraph obtained from G by replacing every edge uv of G by exactly one of the two arcs uv or vu. An oriented graph is an orientation of a graph. Similarly an oriented tree (resp. oriented path) is an orientation of a tree (resp. path).

A proper k-colouring of a digraph is a mapping c from its vertex into {1, . . . , k} such that c(u) = c(v) for every arc uv. A digraph is k-colourable if it admits a proper k-colouring. The chromatic number of a digraph D, denoted χ(D), is the least integer k such that D is k-colourable. A digraph is k-chromatic if its chromatic number equals k.

The focus of our paper is the following natural question: which digraphs are contained in every nchromatic digraph? Such digraphs are called n-universal. Clearly an n-universal digraph has at most n vertices, as every tournament (i.e. orientation of a complete graph) on n vertices is n-chromatic. Since there exist n-chromatic graphs with arbitrarily large girth [START_REF] Erdős | Graph theory and probability[END_REF], n-universal digraphs must be oriented trees.

The celebrated Gallai-Hasse-Roy-Vitaver Theorem [START_REF] Gallai | On directed paths and circuits[END_REF][START_REF] Hasse | Zur algebraischen Begründung der Graphentheorie I[END_REF][START_REF] Roy | Nombre chromatique et plus longs chemins d'un graphe[END_REF][START_REF] Vitaver | Determination of minimal coloring of vertices of a graph by means of Boolean powers of the incidence matrix[END_REF] states that every directed path with n vertices is n-universal. However, it is not the case that every oriented tree on n-vertices is n-universal since there exist (regular) tournaments of order 2k -3 in which every vertex has indegree and outdegree k -2. Such a tournament has chromatic number 2k -3 but has no vertex of out-degree exceeding k -2 and thus does not contain the oriented tree S + k consisting of a vertex dominating k -1 leaves. Burr [START_REF] Burr | Subtrees of directed graphs and hypergraphs[END_REF] considered the function f such that every oriented tree of order k is f (k)-universal. He proved f (k) ≤ (k -1) 2 and conjectured the following bound.

Conjecture 1 (Burr [6]). f (k) = 2k -2; i. e., every oriented tree of order k is (2k -2)-universal.

Since a regular tournament of order 2k -3 does not contain S + k , as Burr remarked, the conjectured bound is best possible.

Conjecture 1 is a generalization of Sumner's conjecture that every oriented tree of order k is contained in every tournament of order 2k -2. Häggkvist and Thomason [START_REF] Häggkvist | Trees in tournaments[END_REF] were the first to show that there was an absolute constant C such that every tournament of order Ck contains every oriented tree of order k. Their bound of Ck was improved to 3k -3 by El Sahili [START_REF] El-Sahili | Trees in tournaments[END_REF], who used a refiniment of an idea in [START_REF] Havet | Median orders: a tool for the second neighborhood problem and Sumner's conjecture[END_REF]. Recently, Kühn, Osthus, and Mycroft [START_REF] Kühn | A proof of Sumner's universal tournament conjecture for large tournaments[END_REF] proved that Sumner's conjecture holds for all sufficiently large k. The proof makes extensive use of results and ideas from a recent paper by the same authors [START_REF] Kühn | An approximate version of Sumner's universal tournament conjecture[END_REF], in which an approximate version of the conjecture was proved.

Despite considerable interest in Burr's conjecture, until this paper there has been no improvement on the bound on f (k) he obtained over thirty years ago. The only progress has been with respect to a few specific classes of paths. El-Sahili proved [START_REF] El-Sahili | Paths with two blocks in k-chromatic digraphs[END_REF] that every oriented path of order 4 is 4-universal and that the antidirected path of order 5 is 5-universal. Addario-Berry, Havet, and Thomassé [START_REF] Addario-Berry | Paths with two blocks in n-chromatic digraphs[END_REF] showed that every oriented path of order k whose vertex set can be partioned into two directed paths is k-universal.

In Section 2, we present several approachs that yield bounds on f (k) matching or improving that given by Burr. Our best bound is obtained by proving and then exploiting the fact that Burr's conjecture holds when restricted to acyclic digraphs. From this we obtain f (k) ≤ k 2 /2 -k/2 + 1. We hope that these approaches will eventually yield even stronger bounds.

In Section 3, we study the universality of antidirected trees; these are oriented trees in which every vertex has in-degree 0 or out-degree 0. Burr [START_REF] Burr | Antidirected subtrees of directed graphs[END_REF] showed that every digraph D with at least 4(k -1)|V (D)| arcs contains all antidirected trees of order k. From this, it follows that every antidirected tree of order k is (8k -7)-universal. We improve this bound to 5k -9 (for k ≥ 2) in Subsection 3.1.

We then consider the smallest integer a(k) such that every digraph D with more than a(k)|V (D)| arcs contains every antidirected tree of order k. The above-mentionned result of Burr asserts a(k) ≤ 4k -4. We conjecture that a(k) = k -2. The value k -2 for a(k) would be best possible, since the oriented tree S + k is not contained in any digraph in which every vertex has outdegree k -2. It is also tight because the complete symmetric digraph K k-1 on k -1 vertices has (k -2)(k -1) arcs but trivially does not contain any oriented tree of order k.

There is no analogue of Conjecture 2 for non-antidirected trees, since a bipartite digraph with bipartition (A, B) such that all the arcs have tail in A and head in B contains no directed paths of length 2.

Hence for any oriented tree T that is not antidirected and any constant C, there is a digraph D with at least C × |V (D)| arcs that does not contain T .

Conjecture 2 for oriented graphs implies Burr's conjecture for antidirected trees. Recall that a (di)graph is k-critical if its chromatic number is k and all its proper sub(di)graphs are (k -1)-colourable. It is well known that every k-critical graph has minimum degree at least k -1. Hence, every (2k -2)critical digraph D is an oriented graph and has minimum degree at least 2k -3. Thus its number of arcs is at least 2k- 3 2 |V (D)|, which exceeds (k -2)|V (D)|. Conjecture 2 may be seen as a directed analogue of the well-known Erdős-Sós conjecture.

Conjecture 3 (Erdős and Sós, 1963[14]). Let G be a graph. Conjecture 3 has been proved in particular cases: when G contains no 4-cycle [START_REF] Saclé | The Erdős-Sós conjecture for graphs without C 4[END_REF] and for trees with diameter at most 4 [START_REF] Mclennan | The Erdős-Sós conjecture for trees of diameter four[END_REF]. Furthermore, using the Regularity Lemma, Ajtai et al. [START_REF] Ajtai | Erdős-Sós Conjecture holds for large k[END_REF] proved that Conjecture 3 is true for sufficiently large k.

If |E(G)| > 1 2 (k -2)|V (G)|,
In Subsection 3.2, we prove Conjecture 2 for antidirected trees of diameter at most 3. This allows us to conclude that every antidirected tree of order k and diameter at most 3 is (2k -3)-universal. We then strengthen this result showing that such trees are actually (2k -4)-universal.

2 Approaches for upper bounds on f (k)

Constructing trees iteratively

Let T be an oriented tree. The in-leaves (resp. out-leaves) of T are the vertices v of T such that d + T (v) = 1 and d - T (v) = 0, (resp. d + T (v) = 0 and d - T (v) = 1). The set of out-leaves (resp. in-leaves) of T is denoted by Out(T ) (resp. In(T )) and its cardinality is denoted by out(T ) (resp. in(T )).

An out-star is an oriented tree T such that T -Out(T ) is a single vertex x. The out-star of order k is denoted S + k . An in-star is defined analagously; the in-star of order k is denoted S - k . In this paper, star is used to mean an out-star or an in-star.

Clearly any digraph D with (k -1)|V (D)| arcs contains both an in-star and out-star of order k. Thus, stars of order k are (2k -1)-universal. In this section, we show that every tree T is g(T ) universal for some function g that depends only on the order of T and how "close" it is to a star.

To this end, we let st(T ) be the minimum number of successive removals of either the set of in-leaves or the set of out-leaves that reduces the oriented tree to a single vertex. Since each such removal removes one or two edges of a longest path, we have diam(T )/2 ≤ st(T ) ≤ diam(T ).

We will show in this section that every oriented tree T of order k is [(2k-3-st(T )) st(T )+2]-universal. We begin with the following simple lemma.

Lemma 4.

Let D be a digraph with both minimum in-degree and minimum out-degree at least k -1, and let T be a tree of order k. For any vertex x of D and vertex t of T , D contains a copy of T in which x corresponds to t.

Proof. We prove the result by induction on k, the result holding trivially when k = 1. Assume now that k ≥ 2. Let v be a leaf of T distinct from t. By symmetry, we may assume that v is an out-leaf. Let u be its in-neighbour in T . By the induction hypothesis, D contains a copy T of T -v in which x corresponds to t. Let y be the vertex corresponding to u in T . Since d + (y) ≥ k -1, there is an out-neighbour z of y not in V (T ). Adding the vertez z and the arc yz to T yields the desired copy of T .

We will need the following slight strengthening of this lemma. Lemma 5. Let D be an oriented graph with both minimum in-degree and minimum out-degree at least k -2, and T a tree of order k. If T has two out-leaves not having a common neighbour, then D contains T .

Proof. Let v 1 and v 2 be two out-leaves of T with v 1 adjacent to u 1 and v 2 adjacent to

u 2 = u 1 . By Lemma 4, D contains a copy T of T -v 1 . Let x 1 , x 2 ,
and y be the vertices of T corresponding to u 1 , u 2 , and v 2 in T -v 1 , respectively. If x 1 has an out-neighbour z 1 in V (D) \ V (T ), then adding z 1 and the arc x 1 z 1 to T yields a copy of T .

So we may assume that all the out-neighbours of x 1 are in V (T ). Since d + (x 1 ) ≥ k -2, the vertex x 1 dominates all the vertices of T -x 1 . In particular, it dominates x 2 and y. Hence the tree T obtained from T by removing the arc x 2 y and adding the arc x 1 y is a copy of T -v 2 . Now x 2 has out-degree at least k -2, and it does not dominate x 1 because D is an oriented graph. Hence x 2 has an out-neighbour z 2 in V (D) \ V (T ). Thus adding z 2 and the arc x 2 z 2 to T yields a copy of T .

We now show how to apply this result to obtain the main result of this section. We begin with four definitions and a simple auxiliary result.

A (di)graph is k-degenerate if all its sub(di)graphs have a vertex of degree at most k. It is well-known and easy to show that every k-degenerate (di)graph is (k + 1)-colourable.

The average degree of a We are now ready to exploit Lemma 5. We prove: Lemma 7. For k ≥ 3, let T be an oriented tree of order k other than

(di)graph G, denoted Ad(G), is v∈V (G) d(v) |V (G)| , which equals 2|E(G)| |V (G)| . The maximum average degree of G, denoted Mad(G), is max{Ad(H) : H ⊆ G}.
S + k . If T -Out(T ) is l-universal, then T is (l + 2k -4)-universal.
Proof. Since T = S + k , it follows that T -Out(T ) has more than one vertex, and thus l ≥ 2. If Out(T ) = ∅, then the result holds trivially, so we assume out(T ) ≥ 1.

Let D be an (l + 2k -4)-chromatic digraph. Without loss of generality, we may assume that D is (l + 2k -4)-critical and hence is connected. Let S be the set of vertices of D with out-degree at most k -2.

Assume first that χ(D -S) ≥ l, so D -S contains a copy T of T -Out(T ). Let v 1 , . . . , v p be the out-leaves of T , and let w 1 , . . . , w p be their respective in-neighbours in T . Now for 1 ≤ i ≤ p, since the out-degree of w i , the vertex corresponding to w i in T , is at least k -1 in D, one can find an out-neighbour

v i of w i in V (D) \ (V (T ) ∪ {v j | 1 ≤ j < i}). Hence D contains T . Assume now that χ(D -S) < l. Since χ(D) = l + 2k -4, we must have χ(D[S]) ≥ 2k -3. If H is a subdigraph of D[S], then v∈V (H) d(v) = 2E(H) ≤ 2 v∈V (H) d + D (v) ≤ (2k -4) × |V (H)|. Hence Mad(D[S]) ≤ 2k -4.
Thus by Lemma 6, D[S] contains a tournament R of order 2k -3. Furthermore, since the out-degree of a vertex in R is at most its out-degree in D[S] and thus is bounded by k -2, every vertex of R has both in-and out-degree equal to k -2 in R. Since all vertices in R have out-degree

at most k -2 in D, each vertex of R has no out-neighbour in V (D) \ V (R). Now, since D is connected, there is an arc xy with x ∈ V (D) \ V (R) and y ∈ V (R).
If T contains an in-leaf v, then let u be its out-neighbour in T . By Lemma 4, R contains a copy of T -v such that u corresponds to y. This copy together with the vertex x and the arc xy is a copy of T in D.

If T contains no in-leaf, then it contains only out-leaves. Moreover, since T = S + k , then T has two leaves that have distinct neighbours. Thus by Lemma 5, R contains T .

The main result of the section now follows easily.

Proposition 8. Every oriented tree T of order k is [(2k -3 -st(T )) st(T ) + 2]-universal.
Proof. Let T 0 , . . . , T st(T ) be a sequence of oriented trees such that T 0 = T , the tree T st(T ) has exactly one vertex tree, and T i is obtained from T i-1 by deleting Out(T i-1 ) or In(T i-1 ), for 1 ≤ i ≤ st(T ). Note that T st(T )-1 is a star and thus is (2|T st(T )-1 | -2)-universal. By successive application of Lemma 7, T is contained in every digraph of chromatic number at least Σ with

Σ = 2|T 0 | -4 + 2|T 1 | -4 + • • • + 2|T st(T )-2 | -4 + 2|T st(T )-1 | -2 = 2 st(T )-1 i=0 |T i | -4 st(T ) + 2. Now for all 0 ≤ i ≤ st(T ) -1, |T i | ≤ k -i, so Σ ≤ (2k -3 -st(T )) st(T ) + 2. Hence T is [(2k -3 -st(T )) st(T ) + 2]-universal.
Proposition 8 implies directly a slightly better bound on f (k) than that obtained by Burr [START_REF] Burr | Subtrees of directed graphs and hypergraphs[END_REF].

Corollary 9. Every oriented tree T of order k is (k 2 -3k + 4)-universal.
Proof. Let T be a tree of order k. If T is a directed path, then it is k-universal by the Gallai-Hasse-Roy-Vitaver Theorem. If T is not a directed path, then st(T ) ≤ k -2. So, by Proposition 8, T is (k 2 -3k + 4)-universal.

Our results show that in order we to determine whether an oriented tree T must exist in digraphs of sufficiently large chromatic number, it would be useful to determine st(T ). However, it is not clear whether this can be done efficiently.

Problem 10. What is the complexity of determining st(T ) for a given an oriented tree T ?

Decomposing digraphs into bikernel-perfect subdigraphs

Let D be a digraph. We say that a set S of vertices of D is dominating if every vertex v in V (D) \ S is dominated by a vertex in S. We say that S is antidominating if every vertex v in V (D) \ S dominates a vertex in S. A dominating stable set is a kernel and an antidominating stable set is an antikernel. If every induced subdigraph of D has a kernel (resp. antikernel), then D is kernel-perfect (resp. antikernel-perfect). A digraph that is both kernel-and antikernel-perfect is said to be bikernel-perfect. Theorem 11. Every oriented tree of order k is contained in every k-chromatic bikernel-perfect digraph.

Proof. Assume the theorem is false and consider a counterexample T of minimum order. Let k be this order and note that trivially k is at least 2.

Let D be a k-chromatic bikernel-perfect digraph, let v be a leaf of T , and let w the unique neighbour of v in T . By symmetry, we may assume that v → w. Since D is bikernel-perfect, it has a kernel S. The digraph D -S has chromatic number at least (k -1), so by induction it contains a copy T of T -v. Now by the definition of a kernel, the vertex w in T corresponding to w is dominated by a vertex v of S. Hence D contains T . Since this holds for all D, T is not a counterexample to the theorem, which is a contradiction.

Several classes of bikernel-perfect digraphs are known. It is easy to show that symmetric digraphs are bikernel-perfect. Richardson [START_REF] Richardson | On weakly ordered systems[END_REF] proved that acyclic digraphs and, more generally, digraphs without directed cycles of odd length are also bikernel-perfect. Several extensions of Richardson's Theorem have been obtained [START_REF] Duchet | Graphes noyau-parfaits[END_REF][START_REF] Duchet | A sufficient condition for a digraph to be kernel-perfect[END_REF][START_REF] Duchet | Une généralisation du théorème de Richardson sur l'existence de noyaux dans les graphes orientés[END_REF][START_REF] Galeana-Sánchez | On kernel-perfect critical digraphs[END_REF]. Sands, Sauer and Woodrow [START_REF] Sands | On monochromatic paths in edge-coloured digraphs[END_REF] showed that a digraph whose arcs may be partitionned into two posets is bikernel-perfect.

We could attempt to find better upper bounds on f (k) by proving that every digraph with sufficiently high chromatic number contains an acyclic (or more generally bikernel-perfect) k-chromatic subdigraph.

Problem 12. What is the minimum integer g(k) such that every g(k)-chromatic digraph has an acyclic k-chromatic subdigraph?

What is the minimum integer g (k) such that every g (k)-chromatic digraph has a bikernel-perfect k-chromatic subdigraph?

Of course, Theorem 11 implies f (k) ≤ g (k), while trivially g (k) ≤ g(k).

Proposition 13. g(k) ≤ k 2 -2k + 2.
Proof. Let D be a (k 2 -2k + 2)-chromatic digraph. Let v 1 , . . . , v l be an ordering of the vertices of D. Let D 1 and D 2 be the digraphs with vertex set V (D) and edge-sets

E(D 1 ) = {v i v j ∈ E(D), i < j} and E(D 2 ) = {v i v j ∈ E(D), i > j}. Clearly, D 1 and D 2 are acyclic and χ(D 1 ) × χ(D 2 ) ≥ χ(D) = k 2 -2k + 2. Hence either D 1 or D 2 has chromatic number at least √ k 2 -2k + 2 = k.
The above proposition implies directly f (k) ≤ k 2 -2k + 2. We now give a better upper bound for f (k).

Theorem 14. f (k) ≤ k 2 /2 -k/2 + 1.

Proof. The results follows easily by induction from

f (1) = 1 if we prove f (k) ≤ f (k -1) + k -1.
Let D be an (f (k -1) + k -1)-chromatic digraph, and T be an oriented tree of order k. Another approach to bounding f (k) would be to prove the existence of a dominating set with not too large chromatic number in any n-chromatic digraph.

Problem 15. What is the minimum integer h(n) such that every n-chromatic digraph has an h(n)chromatic dominating set?

Exploiting acyclic subdigraphs

Let D be a digraph. An acyclic partition of D is a partition of its vertex set (V 1 , . . . , V p ) such that the digraph D[V i ] induced by V i is acyclic. The acyclic number of D, denoted ac(D), is the minimum number of parts of an acyclic partition of D. A proper colouring is an acyclic partition, because a stable set is acyclic. Hence χ(G) ≥ ac(G).

Theorem 16. If T is an oriented tree with vertices v 1 , . . . , v k and D is a digraph with acyclic number k, then for any acyclic partition of

D into k parts V 1 , . . . , V k , D contains a copy of T such that v i ∈ V i for every 1 ≤ i ≤ k.
Proof. We prove the result by induction on k, the result being trivial for k = 1. Let v be a leaf of T . Since we are free to permute the indices of the vertices of T , provided we permute the indices of the parts of the partition using the same permutation, we may assume that v = v k and that the neighbour of v k in T is v k-1 . Moreover, by symmetry, we may assume that v k-1 → v k . Let us now consider

D = D[V 1 ∪ • • • ∪ V k-1 ]. Obviously ac(D ) = k -1, so (V 1 , . . . , V k-1
) is an acyclic partition of D in ac(D ) sets. Hence, by the induction hypothesis, D contains at least one copy of

T = T -v k such that v i ∈ V i for all 1 ≤ i ≤ k -1.
Let S be the set of all vertices of V k-1 that correspond to v k-1 in some such copy of T in D . We will show that there is a vertex s of S that dominates some vertex in V k , which gives the result. Suppose for a contradiction that no vertex of S dominates a vertex of

V k . Now D[V k ∪ S] is acyclic. Consider D = D \ S, so ac(D ) = k -1.
An acyclic partition of D in less than k -1 sets together with S ∪ V k would be an acyclic partition of D in less than k sets, which is impossible. In particular,

S = V k-1 . So (V 1 , . . . , V k-2 , V k-1 \ S)
is an acyclic partition of D into ac(D ) sets. Thus, by the induction hypothesis, D contains a copy of T such that

v i ∈ V i for all 1 ≤ i ≤ k -2 and v k-1 ∈ V k-1 \ S.

The universality of antidirected trees

In [START_REF] Burr | Antidirected subtrees of directed graphs[END_REF], Burr proved that every antidirected tree of order k is contained in every digraph D with at least 4(k -1)|V (D)| arcs. This implies trivially that every antidirected tree of order k is (8k -7)-universal because every (8k -7)-critical digraph D has minimum degree at least 8k -8 and thus has at least 4(k -1)|V (D)| arcs.

In this section, we will first strengthen Burr's result by showing that every antidirected tree of order k is (5k -9)-universal. We then settle Conjecture 2 for antidirected trees of diameter at most 3 which implies that such trees are (2k -3)-universal. We then strengthen the latter result by proving that every such tree is (2k -4)-universal.

An improved upper bound

Let T be an antidirected tree. Let V + (T ) (resp. V -(T )) be the set of vertices with in-degree (resp. out-degree) 0 in T . Clearly (V -(T ), V + (T )) is a partition of V (T ).

Theorem 17. If T is an antidirected tree and D is a digraph with at least (4m(T ) -4)|V (D)| arcs, then

D contains T .
This theorem is a slight strengthening of Burr's result [START_REF] Burr | Antidirected subtrees of directed graphs[END_REF]. Its proof is based on the following three lemmas, the first two of which were proved and used by Burr.

Lemma 18 (Burr [7]). Let G be a bipartite graph and p be an integer. If |E(G)| ≥ p|V (G)|, then G has a subgraph with minimum degree at least p + 1.

Remark 19. This result is tight : for = p m+p > 0, the complete bipartite graph K p,m has p|V (K p,m )|(1-) edges, but every subgraph has minimum degree at most p.

Let (A, B) be a bipartition of the vertex set of a digraph D. We denote by E(A, B) the set of arcs with tail in A and head in B and by e(A, B) its cardinality.

Antidirected trees of diameter 3

In this subsection, we provide evidence for Conjecture 2 by proving that it holds for antidirected trees of diameter at most 3.

We note that it is easy to show that Conjecture 2 holds for antidirected trees of diameter 2 because there are only two antidirected trees of order k and diameter 2: the stars

S + k and S - k . Proposition 26. Let D be a digraph. If |E(D)| > (k -2)|V (D)|, then D contains S + k and S - k . Proof. Let D be a digraph with more than (k -2)|V (D)| arcs. Since v∈V (D) d + (v) = E(D) > (k - 2)|V (D)|, D contains a vertex of out-degree at least k -1. Hence it contains S + k . Similarly, D contains S - k .
Henceforth, we restrict our attention to antidirected trees of diameter 3. An antidirected tree of order k and diameter 3 is made of a central arc uv such that u dominates the out(T ) out-leaves of T and v is dominated by the in(T ) in-leaves of T . Note that out(T ) ≥ 1 and in(T ) ≥ 1, so k = out(T )+in(T )+2 ≥ 4.

Lemma 27. Let D be a digraph, let T be an antidirected tree of diameter 3, and choose uv

∈ E(D). If a) d + (u) ≥ k -1 and d -(v) ≥ in(T ) + 1, or b) d + (u) ≥ k -2, d -(v) ≥ in(T ) + 1 and N -(v) ⊂ N + (u) ∪ {u}, then D contains T . Proof. Set in(T ) = p. Since its in-degree is at least p + 1, the vertex v has at least p in-neighbours v 1 , . . . , v p distinct from u with v 1 ∈ N -(v) \ N + (u) ∪ {u} in case b). Since d + (u) ≥ k -1 or v 1 / ∈ N + (u), the vertex u has k -2 -p = out(T ) out-neighbours in V (D) \ {v, v 1 , . . . , v p }. Hence D contains T .
We will now prove a slight strengthening of Conjecture 2 for antidirected trees of diameter 3. In what follows we write K k for the "complete symmetric" directed graph of order k, with k vertices and an arc in each direction joining each pair of vertices. Proof. We prove the result by induction on |V (D)|. Fix an antidirected tree T of order k and diameter 3. Let V + (resp. V -) be the set of vertices of D of out-degree (resp. in-degree) at least k -1.

If

V + = V -= ∅, then every vertex v satisfies d + (v) = d -(v) = k -2. If D is not K k-1
, then it is not complete symmetric and has at least k vertices. Thus there exist three vertices u, v and v 1 such that uv ∈ E(D), v 1 v ∈ E(D), and uv 1 / ∈ E(D). In this case u and v satisfy the condition b) of Lemma 27, and hence D contains T .

It remains to consider the case that V + or V -is non-empty. By symmetry, we may assume that V + = ∅. If V -= ∅, then every vertex has in-degree k -2. Picking a vertex u ∈ V + and one of its out-neighbours v, Lemma 27 gives the result because k -2 ≥ in(T ). We may therefore assume that V + and V -are both nonempty.

Let u be a vertex of out-degree at least k -1 and v an out-neighbour of u. If d -(v) ≥ in(T ) + 1, then Lemma 27 gives the result. Hence we may assume that every out-neighbour of u has in-degree at most in(T ). In particular, the set V 1 of vertices of D with in-degree at most in(T ) has size at least k -1. Analogously, we may assume that the set V 2 of vertices of D with out-degree at most out(T ) has size at least k -1.

If

V 1 ∩ V 2 contains some vertex v, then d(v) ≤ in(T ) + out(T ) = k -2. Hence |E(D -v)| ≥ (k -2)|V (D -v)|
and, by the induction hypothesis, T is contained in D -v (and so in D) unless

D -v = K k-1 . In this case d(v) = k -2,
and it is easy to see that D contains T . Hence we may assume that

V 1 ∩ V 2 = ∅. Now suppose that there exist v 1 ∈ V 1 and v 2 ∈ V 2 such that v 1 v 2 is
+ (v 2 ) leaving v 2 and v 1 v 2 / ∈ E(D)). Now d -(v 1 ) + d + (v 2 ) ≤ in(T ) + out(T ) = k -2, so |E(D )| ≥ (k -2)|V (D )|. If D = K k-1
, by the induction hypothesis, D contains a copy of T . This copy may be transformed into a copy of T in D, by replacing

t by v 1 (resp. v 2 ) if t is a source (resp. a sink) in T . If D = K k-1 then D -{v 1 , v 2 } = K k-2 . Since d + (v 1 ) ≥ out(T ) + 1 and d -(v 2 ) ≥ in(T ) + 1, one can again easily see that D contains T .
The only remaining case is that for all u ∈ V 1 and v ∈ V 2 , uv is an arc of C. In this case, every vertex u ∈ V 1 has out-degree at least k -1 and every vertex v ∈ V 2 has in-degree at least k -1. Applying Lemma 27 to any edge uv with u ∈ V 1 and v ∈ V 2 then shows that D contains T .

Theorem 28 implies that every connected digraph D with minimum degree at least 2k -4 other than K k-1 contains every antidirected tree of order k and diameter 3. In particular, this is the case if D is (2k -3)-critical. Hence antidirected trees of order k and diameter 3 are (2k -3)-universal. We will now improve this result slightly by showing that such trees are (2k -4)-universal.

Proposition 29. Every oriented graph with minimum degree at least 2k -5 contains every antidirected tree of order k of diameter 3.

Proof. Suppose for a contradiction that there is some antidirected tree T of order k and diameter 3 that is not contained in some oriented digraph D with minimum degree 2k -5.

Assume first that k = 4. In this case, T is the antidirected path of length 3.

If D contains no vertex of out-degree 2, then consider any vertex x of out-degree at least 3. By Lemma 27, each out-neighbour of x has in-degree 1. Thus its out-degree is at least 2, and so it is at least 3 by our assumption. The oriented graph induced by the vertices of out-degree at least 3 now contains a vertex of in-degree at least 3. Hence there is an arc uv such that d + (u) ≥ 3 and d -(v) ≥ 3, and it follows from Lemma 27 that D contains T , a contradiction.

If D contains some vertex of out-degree exactly 2, then let a be some such vertex and let b and c be its out-neighbours. Vertex b has no in-neighbour u not in {a, c} for otherwise (u, b, a, c) is a copy of T . Similarly, vertex c has no in-neighbour u not in {b, c} for otherwise (u, c, a, b) is a copy of T . We claim that there is no arc joining b and c. Suppose that some such arc bc exists. Since Assume now that k ≥ 5. By symmetry, we may assume that in(T ) ≤ out(T ), so in(T ) ≤ k -4. Let V + be the set of vertices of out-degree at least k -1. We claim that V + = ∅; suppose that V + = ∅.

If there is no arc uv with u ∈ V + and v / ∈ V + , then each vertex of V + has all its out-neighbours in V + . In this case, the digraph D + induced by V + has at least |V + |(k -1) arcs and thus has at least a vertex v of in-degree k -1 in D + . Let u be any in-neighbour of v in D + . As d + (u) ≥ k -1, applying Lemma 27 to uv yields a contradiction. Hence we may assume that there is an arc uv with u ∈ V + and v / ∈ V + , in which case d + (v) ≤ k -2 and so d -(v) ≥ k -3. Since in(T ) ≤ k -4, applying Lemma 27 to uv again gives a contradiction. This proves the claim that V + = ∅.

Since V + = ∅, every vertex has out-degree at most k -2 and thus in-degree at least k -3. We claim that there is a vertex u of out-degree k -2 dominating a vertex of in-degree at least k -2. If this is not the case, then every vertex of out-degree k -2 has all its out-neighbours of in-degree at most k -3 and thus out-degree at least k -2. This implies that V 2 , the set of vertices of out-degree k -2, has no outgoing arcs, and thus there is a vertex v in V 2 with in-degree at least k -2 in D[V 2 ]. Picking any in-neighbour u of v in V 2 , we obtain the desired vertices, a contradiction.

Finally, by Lemma 27 and our assumption that D does not contain T , for every out-neighbour w of u, we must have N -(w) ⊂ N + (u) ∪ {u}. Since each vertex has in-degree at least k -3 and v has in-degree k -2, the digraph D[N + (u)] has at least (k -2)(k -4) + 1 > k-2 2 arcs, which is impossible since D is an oriented graph.

Note that the analogue of Proposition 29 does not holds for digraphs (rather than oriented graphs). Indeed, there are connected digraphs such that d(v) ≥ 2k -5 for every vertex v that do not contain every antidirected tree of order k of diameter 3. For example, let G be a regular bipartite graph of degree k -3 with bipartition (A, B). Let D the digraph obtained from G by orienting all the edges from A to B and adding, for each a ∈ A (resp. b ∈ B) a copy of K k-2 dominating a (resp. dominated by b). One can easily check that for every vertex v, d + (v) + d -(v) ≥ 2k -5, but D does not contain the antidirected tree of order k and diameter 3 with one in-leaf.

We close by noting the following consequence of Proposition 29.

Corollary 30. Every antidirected tree of order k and diameter 3 is (2k -4)-universal.

Proof. If D is a (2k -4)-chromatic digraph, then D contains a (2k -4)-critical oriented graph D , in which every vertex has degree at least 2k -5. Hence D , and thus also D, contains every antidirected tree of order k of diameter 3, by Proposition 29.

Corollary 30 and Proposition 29 are tight. A regular tournament of order 2k -5 is (2k -5)-chromatic and is an oriented graph with minimum degree 2k -6, but it does not contain the antidirected tree with k -3 out-leaves, since no vertex has out-degree k -2 or more.

Conjecture 2 .

 2 Let D be a digraph. If |E(D)| > (k -2)|V (D)|, then D contains every antidirected tree of order k.

Lemma 6 .

 6 If G is a graph of maximum average degree at most k, where k is an integer with k ≥ 3, then χ(G) ≤ k or G contains a complete graph on k + 1 vertices. Proof. If χ(G) > k, then G contains a (k + 1)-critical graph H. Since δ(H) ≥ k and Mad(G) ≤ k, the subgraph H must be k-regular. Because χ(H) = k + 1, by Brooks' Theorem, H is a complete graph on k + 1 vertices.

  Let A be a maximal acyclic induced subdigraph of D. If χ(A) ≥ k, then by Theorem 11, A contains T , so D contains T . If χ(A) ≤ k -1, then χ(D -A) ≥ f (k -1). Let v be a leaf of T . The digraph D -A contains T -v. Now, by maximality of A, for every vertex x of D -A there are vertices y and z of A such that xy and zx are arcs. So we can extend T -v to T by adding a vertex to A.

  This contradicts the definition of S. Theorem 16 and Theorem 11 yield f (k) ≤ (k -1) 2 + 1, as follows. Let D be a ((k -1) 2 + 1)-chromatic digraph D, and let T be an oriented tree of order k. If ac(D) ≥ k, by Theorem 16, D contains T . If not, then in an acyclic partition into ac(D) sets, one of the sets induces an acyclic digraph with chromatic number at least k and by Theorem 11, D contains T .

Theorem 28 .

 28 Let D be a connected digraph. If |E(D)| ≥ (k -2)|V (D)| and D = K k-1 , then D contains every antidirected tree of order k and diameter 3.

  not an arc of D. Consider the digraph D obtained by replacing the two vertices v 1 and v 2 by a vertex t dominating the out-neighbours of v 1 and dominated by the in-neighbours of v 2 . The digraph D has one vertex less than D and at most d -(v 1 ) + d + (v 2 ) arcs less than D (the d -(v 1 ) entering v 1 , the d

  d(b) ≥ 3, b has a neighbour u distinct from a and c. By the above observation, u is an out-neighbour of b, so (a, c, b, u) is a copy of T , a contradiction. It follows that d -(b) = d -(c) = 1, and thus d + (b) = d + (c) = 2. Hence the oriented graph induced by the vertices of out-degree 2 contains a vertex of in-degree at least 2. Now there is an arc uv such that d + (u) ≥ 2 and d -(v) ≥ 2. Moreover, by the above claim, N -(v) ∩ N + (u) = ∅. Together with Lemma 27, this again yields a contradiction.

  then G contains every tree of order k .In fact, Conjecture 2 for symmetric digraphs is equivalent to Conjecture 3. Consider a graph G and its corresponding symmetric digraph D (the digraph obtained from G by replacing each edge uv by the two arcs uv and vu). Note that G has more than 1 2 (k -2)|V (G)| edges if and only if |E(D)| > (k -2)|V (D)|. Furthermore, if T is a tree and T is one of its (two) antidirected orientations, then it is easy to check that G contains T if and only if D contains T .

Partly supported by ANR Blanc AGAPE ANR-09-BLAN-0159 and the INRIA/FUNCAP exchange programme. Partly supported by the INRIA/FUNCAP exchange programme. Partly supported by ANR Blanc AGAPE ANR-09-BLAN-0159

Lemma 20 (Burr [7]). Every digraph D contains a partition (A, B) such that e(A, B) ≥ |E(D)|/4.

We set m(T ) = max{|V + (T )|, |V -(T )|}.

Lemma 21. Let T be an antidirected tree and let D be a bipartite graph with bipartition (A, B) such that every vertex in A has out-degree at least m(T ) and every vertex in B has in-degree at least m(T ). Then D contains T .

Proof. We show by induction on |T | that one may find a copy of T such that every vertex of

Let v be a leaf of T . By symmetry, we may assume that v is an in-leaf, so Proof. If T is a star, then it is (2k -2)-universal, which is more than we need.

If T is not a star, then Corollary 22 and Theorem 24 yield that T is (min{8m(T )-7; 10k-8m(T )-11})universal. The first function increases with m(T ) and the second decreases with m(T ). They are equal when m(T ) = 5 8 k -1 4 . In this case, their common value is 5k -9.