A note on tree-cycle Ramsey numbers

2026/07/20 by Ting Huang, Yanbo Zhang, Yaojun Chen
#math.CO

paper · pdf

Abstract

Let R(T_n,C_m) denote the Ramsey number of a tree T_n on n vertices versus a cycle C_m of length m. Burr, Erdős, Faudree, Rousseau, and Schelp (1982) asked for the least function f(m) such that R(T_n,C_m)=2n-1 for every odd m≥ 3 whenever n≥ f(m). They proved that f(m)≤ 756m¹⁰. This bound was later improved to 25m by Brennan (2016) and to 4m-8 by Fan and Lin (2025). In this note, we show that f(m)≤ 2m-4 by using a different method and conjecture that f(m)=\lceil (2m-1)/3\rceil.

Related

• Ramsey numbers of trees versus odd cycles
• The Ramsey Number for Tree Versus Wheel with Odd Order
• The Ramsey numbers for trees of order n with maximum degree at least n-5 versus the wheel graph of order nine
• Ramsey numbers of trees
• On the size Ramsey number of all cycles versus a path