Ramsey numbers of trees versus odd cycles (Q726660): Difference between revisions

Summary: \textit{S. A. Burr} et al. [Trans. Am. Math. Soc. 269, 501--512 (1982; Zbl 0543.05047)] initiated the study of Ramsey numbers of trees versus odd cycles, proving that \(R(T_n, C_m) = 2n - 1\) for all odd \(m \geqslant 3\) and \(n \geqslant 756m^{10}\), where \(T_n\) is a tree with \(n\) vertices and \(C_m\) is an odd cycle of length \(m\). They proposed to study the minimum positive integer \(n_0(m)\) such that this result holds for all \(n \geqslant n_0(m)\), as a function of \(m\). In this paper, we show that \(n_0(m)\) is at most linear. In particular, we prove that \(R(T_n, C_m) = 2n - 1\) for all odd \(m \geqslant 3\) and \(n \geqslant 25m\). Combining this with a result of \textit{R. J. Faudree} et al. [Discrete Math. 10, 269--277 (1974; Zbl 0293.05120)] yields \(n_0(m)\) is bounded between two linear functions, thus identifying \(n_0(m)\) up to a constant factor.