Skip to content
Preprint

A near-linear upper bound for Burr's conjecture

Sep 2026 · 0 citations · 19 references
Mathematics

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)\le (k-1)^2$ and conjectured that $f(k)=2k-2$. Bessy, Gon\c{c}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)\le \lfloor 31\log (k!)\rfloor=O(k\log k)$.

View source

Similar papers

Preprint Aug 2026

A new lower bound for two-color van der Waerden numbers

The van der Waerden number $w(k)$ is the smallest positive integer $N$ such that every two-coloring of $\{1,2,\ldots,N\}$ contains a monochromatic $k$-term arithmetic progression. We prove that $w(k) \geq (1-o(1))k2^{k-1}$ holds for all positive integers $k$. This verifies a conjecture of Erd\H{o}s. In 1968, Berlekamp...

Marcelo Campos, Jacob Fox, C. Schildkraut · 0 citations
Preprint Sep 2026

Upper bounds for ordered Ramsey numbers of forests and bounded-degree graphs

We prove the following two upper bounds for ordered Ramsey numbers: (1) Every ordered forest $F$ on $n$ vertices satisfies $R_{<}(F,F)=O(n^{1+\lceil\log\chi_{<}(F)\rceil})$. This in particular answers a question of Geneson, Holmes, Liu, Neidinger, Pehova and Wass. (2) There is a function $f$ such that, for every fixed...

Lior Gishboliner, Xiang-Yu Li · 0 citations
Preprint Sep 2026

An improved upper bound for oriented diameter of graphs with diameter $4$

Let $f(d)$ denote the smallest integer such that every bridgeless graph of diameter $d$ admits a strong orientation with diameter at most $f(d)$. It is known that $f(2)=6$ and $f(3)=9$. For $d=4$, the classical bounds of Chv\'{a}tal and Thomassen [JCTB, 1978] imply $12\le f(4)\le40$, and subsequent work reduced the upp...

Yao-Kun Feng, Hui Lei, Xiao-Pan Lian et al. · 0 citations
Preprint Sep 2026

An Improved Upper Bound for Multicolour Ramsey Numbers

Let $R_r(k)$ denote the diagonal $r$-colour Ramsey number. We prove that there exist absolute constants $c,K>0$ such that $R_r(k)\le r^{rk}\exp\!\left(-c\frac{k}{r\log^2(2r)}\right)$ for every $r\ge2$ and every $k\ge Kr^2\log^6(2r)$. This improves the exponential saving in a recent bound of Yang and Mao by a factor of...

Sunghyeon Jo · 1 citation
Preprint Sep 2026

The Burr-Erd\H{o}s-Graham-S\'os conjecture for the seven-cycle

For a graph $H$, let $f(n,e,H)$ be the least number of colors in an edge-coloring of some $n$-vertex graph with at least $e$ edges in which every copy of $H$ is rainbow. Burr, Erd\H{o}s, Graham, and S\'os conjectured that $f(n,\lfloor n^2/4\rfloor+1,C_{2k+1})=(1/8+o(1))n^2$ for every fixed $k\ge3$, and Buci\'c, Chen, a...

Asad Shahab · 0 citations
Preprint Sep 2026

A Bound Below 2.8 for Tuza's Conjecture

Let $\nu(G)$ be the maximum number of edge-disjoint triangles in a graph $G$ and $\tau(G)$ the minimum number of edges meeting every triangle. Tuza conjectured that $\tau(G)\le 2\nu(G)$. We prove that $\tau(G)\le (165/59)\nu(G)$. The constant $165/59\approx 2.797$ improves the bound $66/23\approx 2.870$ that Haxell pro...

Si-Chen Wang · 1 citation

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.