Burr’s conjecture

Burr’s conjecture asserts that every oriented tree with $k$ vertices occurs in every digraph of chromatic number $2k-2$. The value $2k-2$ is best possible, but the general assertion remains open.

Known results

• Burr proved the general upper bound $(k-1)^2$.
• Addario-Berry, Havet, Linhares-Sales, Reed, and Thomassé (2013) improved this to $\frac{k^2}{2}-\frac{k}{2}+1$.
• Bessy, Gonçalves, and Reinald (2024) obtained a subquadratic bound of $8\sqrt{\frac{2}{15}}k\sqrt{k}+\frac{11}{3}k+\sqrt{\frac{5}{6}}\sqrt{k}+1$.
• Linear bounds are known for some oriented-path classes and all oriented stars.

September 16, 2026 near-linear bound

Liangdong Fan, Junying Lu, and Yaojun Chen report an absorbing-set argument proving $f(k)\le \lfloor31\log(k!)\rfloor$, the first reported near-linear general bound. This substantially narrows the gap to $2k-2$, but does not prove Burr’s conjecture; the advance is unverified here.

Current status (as of September 2026): Burr’s conjectured threshold $2k-2$ remains unproved, while a new preprint claims the near-linear upper bound $f(k)\le\lfloor31\log(k!)\rfloor$.