In 1980, Burr conjectured that every directed graph with chromatic number 2 k − 2 contains any oriented tree of order k as a subdigraph. Burr showed that chromatic number ( k − 1 ) 2 suffices, and this was later improved to k 2 2 − k 2 + 1 by Addario-Berry, Havet, Linhares-Sales, Reed and Thomassé. We prove the first subquadratic bound for Burr's conjecture: every digraph with chromatic number 8 3 k k + 7 k contains any oriented tree of order k . Moreover, we provide improved bounds of 4 / 3 k k + k / 2 for arborescences, and ( b + 3 ) 2 k for paths with b blocks.
No takes yet. Share an insight, caveat, or question.
Bessy et al. (2026) studied this question.
Synapse has enriched 2 closely related papers on similar clinical questions. Consider them for comparative context: