Skip to content
DraconiticResearch
Search Sources API
181,713 studies31 sourcesUpdated 19 min ago
PreprintarXiv licencearXiv

A near-linear upper bound for Burr's conjecture

  • Liangdong Fan
  • Junying Lu
  • Yaojun Chen
Open at sourcePDFDOICite

Abstract

Let f(k) denote the smallest integer such that every oriented graph D with chromatic number at least f(k) contains every oriented tree on k vertices. Burr (1980) showed that f(k)≤ (k−1)2 and conjectured that f(k)=2k−2. Bessy, Gonçalves and Reinald (2025) proved that f(k)=O(k3/2). In this paper, by using an absorbing set method, we show that f(k)≤ ⌊ 31log (k!)⌋=O(klog k).

Related

  1. A near-linear upper bound for the Yellowstone permutation: a(n) <= n (ln n)^7 for every n >= 3
    Tomer Haver
    Zenodo (CERN European Organization for Nuclear Research)Peer-reviewedCC BY5 citedAlgebra & number theoryOpenAlex
  2. An Improvement to the Upper Bound for Marton's Covering Conjecture
    Zhao Song, Song Yue
    arXivPreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Conway's thrackle conjecture: a new upper bound of 4/3n
    Dániel Gábor Simon
    arXivPreprintCC BY-SA 4.0Full textCombinatorics & discrete mathematicsGeometry & topologyarXiv
  4. A linear upper bound for Berge saturation numbers
    Tianying Xie
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. AN IMPROVED UPPER BOUND FOR THE SMALLEST COUNTEREXAMPLE TO THE MERTENS CONJECTURE
    Zhenyu Bi, Enze Hou
    HALPreprintCC BY 4.0Full textAlgebra & number theoryHAL

Cite

BibTeXRIS
BibTeX
@misc{fan2026nearlinear,
  title = {{A near-linear upper bound for Burr's conjecture}},
  author = {Liangdong Fan and Junying Lu and Yaojun Chen},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.18175},
  eprint = {2609.18175},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.18175},
}
RIS
TY  - UNPB
TI  - A near-linear upper bound for Burr's conjecture
AU  - Liangdong Fan
AU  - Junying Lu
AU  - Yaojun Chen
PY  - 2026
DA  - 2026/09/16
PB  - arXiv
DO  - 10.48550/arxiv.2609.18175
UR  - https://arxiv.org/abs/2609.18175
AB  - Let f(k) denote the smallest integer such that every oriented graph D with chromatic number at least f(k) contains every oriented tree on k vertices. Burr (1980) showed that f(k)≤ (k−1)^2 and conjectured that f(k)=2k−2. Bessy, Gonçalves and Reinald (2025) proved that f(k)=O(k^3/2). In this paper, by using an absorbing set method, we show that f(k)≤ ⌊ 31log (k!)⌋=O(klog k).
ER  -