×

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
PDF BibTeX XML Cite
Full Text: DOI