Oriented trees in O(kk)-chromatic digraphs, a subquadratic bound for Burr's conjecture
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.
Authors
- Stéphane Bessy (ORCID: https://orcid.org/0000-0001-7130-4990)
- Amadeus Reinald (ORCID: https://orcid.org/0000-0002-8108-4036)
- Daniel Gonçalves
Institutions
- Centre National de la Recherche Scientifique (FR)
- Université de Montpellier (FR)
- Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier (FR)
Publication Details
- Journal
- Journal of Combinatorial Theory Series B
- Published
- 2026-09-30
- DOI
- https://doi.org/10.1016/j.jctb.2026.09.007
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00