Czechoslovak Mathematical Journal, Vol. 71, No. 2, pp. 351-372, 2021
Ramsey numbers for trees II
Zhi-Hong Sun
Received July 24, 2019. Published online March 5, 2021.
Abstract: Let $r(G_1, G_2)$ be the Ramsey number of the two graphs $G_1$ and $G_2$. For $n_1\ge n_2\ge1$ let $S(n_1,n_2)$ be the double star given by $V(S(n_1,n_2))=\{v_0,v_1,\ldots,v_{n_1},w_0$, $w_1,\ldots,w_{n_2}\}$ and $E(S(n_1,n_2))=\{v_0v_1,\ldots,v_0v_{n_1},v_0w_0, w_0w_1,\ldots,w_0w_{n_2}\}$. We determine $r(K_{1,m-1},$ $S(n_1,n_2))$ under certain conditions. For $n\ge6$ let $T_n^3=S(n-5,3)$, $T_n"=(V,E_2)$ and $T_n"' =(V,E_3)$, where $V=\{v_0,v_1,\ldots,v_{n-1}\}$, $E_2=\{v_0v_1,\ldots,v_0v_{n-4},v_1v_{n-3}$, $v_1v_{n-2}, v_2v_{n-1}\}$ and $E_3=\{v_0v_1,\ldots, v_0v_{n-4},v_1v_{n-3},$ $v_2v_{n-2},v_3v_{n-1}\}$. We also obtain explicit formulas for $r(K_{1,m-1},T_n)$, $r(T_m',T_n)$ $(n\ge m+3)$, $r(T_n,T_n)$, $r(T_n',T_n)$ and $r(P_n,T_n)$, where $T_n\in\{T_n",T_n"',T_n^3\}$, $P_n$ is the path on $n$ vertices and $T_n'$ is the unique tree with $n$ vertices and maximal degree $n-2$.
References: [1] S. A. Burr, P. Erdős: Extremal Ramsey theory for graphs. Util. Math. 9 (1976), 247-258. MR 0429622 | Zbl 0333.05119
[2] G. Chartrand, L. Lesniak: Graphs and Digraphs. Wadsworth & Brooks/Cole Mathematics Series. Wadsworth & Brooks/Cole Advanced Books & Software, Monterey (1986). DOI 10.1201/b19731 | MR 0834583 | Zbl 0666.05001
[3] R. J. Faudree, R. H. Schelp: Path Ramsey numbers in multicolorings. J. Comb. Theory, Ser. B 19 (1975), 150-160. DOI 10.1016/0095-8956(75)90080-5 | MR 0412023 | Zbl 0286.05111
[4] J. W. Grossman, F. Harary, M. Klawe: Generalized Ramsey theory for graphs, X: Double stars. Discrete Math. 28 (1979), 247-254. DOI 10.1016/0012-365X(79)90132-8 | MR 0548624 | Zbl 0434.05052
[5] Y. Guo, L. Volkmann: Tree-Ramsey numbers. Australas. J. Comb. 11 (1995), 169-175. MR 1327331 | Zbl 0828.05043
[6] F. Harary: Recent results on generalized Ramsey theory for graphs. Graph Theory and Applications. Lecture Notes in Mathematics 303. Springer, Berlin (1972), 125-138. DOI 10.1007/BFb0067364 | MR 0342431 | Zbl 0247.05118
[7] L. K. Hua: Introduction to Number Theory. Springer, Berlin (1982). DOI 10.1007/978-3-642-68130-1 | MR 0665428 | Zbl 0483.10001
[8] S. P. Radziszowski: Small Ramsey numbers. Electron. J. Comb. 2017 (2017), Article ID DS1, 104 pages. DOI 10.37236/21
[9] Z.-H. Sun: Ramsey numbers for trees. Bull. Aust. Math. Soc. 86 (2012), 164-176. DOI 10.1017/S0004972711003388 | MR 2960237 | Zbl 1247.05150
[10] Z.-H. Sun, Y.-Y. Tu: Turán's problem for trees $T_n$ with maximal degree $n-4$. Available at https://arxiv.org/abs/1410.7282 (2014), 28 pages.
[11] Z.-H. Sun, L.-L. Wang: Turán's problem for trees. J. Comb. Number Theory 3 (2011), 51-69. MR 2908182 | Zbl 1247.05117
[12] Z.-H. Sun, L.-L. Wang, Y.-L. Wu: Turán's problem and Ramsey numbers for trees. Colloq. Math. 139 (2015), 273-298. DOI 10.4064/cm139-2-8 | MR 3337221 | Zbl 1312.05089
Affiliations: Zhi-Hong Sun, School of Mathematics and Statistics, Huaiyin Normal University, 111 Changjiang West Road, Huaian, Jiangsu 223300, P. R. China, e-mail: zhsun@hytc.edu.cn
