Ramsey numbers of trees
read the original abstract
We show that there exists a constant $c>0$ such that every $n$-vertex tree $T$ with $\Delta(T)\le cn$ has Ramsey number $R(T)=\max\{t_1+2t_2,2t_1\}-1$, where $t_1\ge t_2$ are the sizes of the bipartition classes of $T$. This improves an asymptotic result of Haxell, {\L}uczak, and Tingley from 2002, and shows that, though Burr's 1974 conjecture on the Ramsey numbers of trees has long been known to be false for certain `double stars', it is true for trees with up to small linear maximum degree.
This paper has not been read by Pith yet.
Forward citations
Cited by 2 Pith papers
-
On Balance, To What Degree is Burr's Conjecture True?
For lopsided trees with t2 >= 2 t1, Burr's bound has a gap of order max(t1^2/t2, sqrt(t1)); for t2 >= 500 t1 the bound is tight if Delta(T) <= t2 - t1 but off by Omega(log t2) otherwise.
-
A degree version of the Burr-Erd\H{o}s conjecture on trees
Proves that graphs on N ≥ 2n vertices with δ(G) ≥ ⌊3N/4⌋ have every 2-edge-coloring containing a monochromatic copy of every n-vertex tree with max degree ≤ Δ.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.