Geodesic
Ramsey numbers for trees II
Czechoslovak Mathematical Journal, Tome 71 (2021) no. 2, pp. 351-372
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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$.
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$.
DOI : 10.21136/CMJ.2021.0328-19
Classification : 05C05, 05C35, 05C55
Keywords: Ramsey number; tree; Turán's problem 
@article{10_21136_CMJ_2021_0328_19,
     author = {Sun, Zhi-Hong},
     title = {Ramsey numbers for trees {II}},
     journal = {Czechoslovak Mathematical Journal},
     pages = {351--372},
     year = {2021},
     volume = {71},
     number = {2},
     doi = {10.21136/CMJ.2021.0328-19},
     mrnumber = {4263174},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2021.0328-19/}
}
TY  - JOUR
AU  - Sun, Zhi-Hong
TI  - Ramsey numbers for trees II
JO  - Czechoslovak Mathematical Journal
PY  - 2021
SP  - 351
EP  - 372
VL  - 71
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2021.0328-19/
DO  - 10.21136/CMJ.2021.0328-19
LA  - en
ID  - 10_21136_CMJ_2021_0328_19
ER  - 
%0 Journal Article
%A Sun, Zhi-Hong
%T Ramsey numbers for trees II
%J Czechoslovak Mathematical Journal
%D 2021
%P 351-372
%V 71
%N 2
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2021.0328-19/
%R 10.21136/CMJ.2021.0328-19
%G en
%F 10_21136_CMJ_2021_0328_19
Sun, Zhi-Hong. Ramsey numbers for trees II. Czechoslovak Mathematical Journal, Tome 71 (2021) no. 2, pp. 351-372. doi: 10.21136/CMJ.2021.0328-19

[1] Burr, S. A., Erdős, P.: Extremal Ramsey theory for graphs. Util. Math. 9 (1976), 247-258. | MR | JFM

[2] Chartrand, G., Lesniak, L.: Graphs and Digraphs. Wadsworth & Brooks/Cole Mathematics Series. Wadsworth & Brooks/Cole Advanced Books & Software, Monterey (1986). | DOI | MR | JFM

[3] Faudree, R. J., Schelp, R. H.: Path Ramsey numbers in multicolorings. J. Comb. Theory, Ser. B 19 (1975), 150-160. | DOI | MR | JFM

[4] Grossman, J. W., Harary, F., Klawe, M.: Generalized Ramsey theory for graphs, X: Double stars. Discrete Math. 28 (1979), 247-254. | DOI | MR | JFM

[5] Guo, Y., Volkmann, L.: Tree-Ramsey numbers. Australas. J. Comb. 11 (1995), 169-175. | MR | JFM

[6] Harary, F.: Recent results on generalized Ramsey theory for graphs. Graph Theory and Applications Lecture Notes in Mathematics 303. Springer, Berlin (1972), 125-138. | DOI | MR | JFM

[7] Hua, L. K.: Introduction to Number Theory. Springer, Berlin (1982). | DOI | MR | JFM

[8] Radziszowski, S. P.: Small Ramsey numbers. Electron. J. Comb. 2017 (2017), Article ID DS1, 104 pages. | DOI | MR

[9] Sun, Z.-H.: Ramsey numbers for trees. Bull. Aust. Math. Soc. 86 (2012), 164-176. | DOI | MR | JFM

[10] Sun, Z.-H., Tu, Y.-Y.: Turán's problem for trees $T_n$ with maximal degree $n-4$. Available at , 28 pages. | arXiv

[11] Sun, Z.-H., Wang, L.-L.: Turán's problem for trees. J. Comb. Number Theory 3 (2011), 51-69. | MR | JFM

[12] Sun, Z.-H., Wang, L.-L., Wu, Y.-L.: Turán's problem and Ramsey numbers for trees. Colloq. Math. 139 (2015), 273-298. | DOI | MR | JFM

Cité par Sources :