Ramsey numbers for trees II

Sun, Zhi-Hong

Czechoslovak Mathematical Journal, Tome 71 (2021) no. 2, pp. 351-372.

Résumé

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\ge 1$ 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\ge 6$ 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$.

Détail

DOI : 10.21136/CMJ.2021.0328-19

Classification : 05C05, 05C35, 05C55
Keywords: Ramsey number; tree; Turán's problem