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.
Asymptotics of Ramsey numbers of double stars
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
abstract
A double star $S(n,m)$ is the graph obtained by joining the center of a star with $n$ leaves to a center of a star with $m$ leaves by an edge. Let $r(S(n,m))$ denote the Ramsey number of the double star $S(n,m)$. In 1979 Grossman, Harary and Klawe have shown that $$r(S(n,m)) = \max\{n+2m+2,2n+2\}$$ for $3 \leq m \leq n\leq \sqrt{2}m$ and $3m \leq n$. They conjectured that equality holds for all $m,n \geq 3$. Using a flag algebra computation, we extend their result showing that $r(S(n,m))\leq n+ 2m + 2$ for $m \leq n \leq 1.699m$. On the other hand, we show that the conjecture fails for $\frac{7}{4}m +o(m)\leq n \leq \frac{105}{41}m-o(m)$. Our examples additionally give a negative answer to a question of Erd\H{o}s, Faudree, Rousseau and Schelp from 1982.
fields
math.CO 2years
2026 2verdicts
UNVERDICTED 2representative citing papers
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 ≤ Δ.
citing papers explorer
-
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 ≤ Δ.