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

Institutions

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
article

Oriented trees in O(kk)-chromatic digraphs, a subquadratic bound for Burr's conjecture

Stéphane Bessy, Amadeus Reinald, Daniel Gonçalves
Journal of Combinatorial Theory Series B
Advanced Graph Theory Research
article

Oriented trees in O(kk)-chromatic digraphs, a subquadratic bound for Burr's conjecture

Stéphane Bessy, Amadeus Reinald, Daniel Gonçalves
article en

Abstract

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.

Journal of Combinatorial Theory Series BVol. 182
Centre National de la Recherche Scientifique (FR), Université de Montpellier (FR), Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier (FR)
Openalex Percentile: Top 9%
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Oriented trees in O(kk)-chromatic digraphs, a subquadratic bound for Burr's conjecture — Stéphane Bessy, Amadeus Reinald, et al. · Journal of Combinatorial Theory Series B (2026) | TGRS Research Map | TGRS