# zbMATH — the first resource for mathematics

Oriented trees in digraphs. (English) Zbl 1262.05066
Summary: 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)\leq (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)\leq 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 $$|E(D)|>(k-2)|V(D)|$$, then the digraph DD 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.

##### MSC:
 05C20 Directed graphs (digraphs), tournaments 05C05 Trees 05C15 Coloring of graphs and hypergraphs
Full Text: