Geodesic
On the Ramsey numbers of non-star trees versus connected graphs of order six
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 2, pp. 331-349 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

This paper completes our studies on the Ramsey number r(T_n,G) for trees T_n of order n and connected graphs G of order six. If χ(G) ≥ 4, then the values of r(T_n,G) are already known for any tree T_n. Moreover, r(S_n,G), where S_n denotes the star of order n, has been investigated in case of χ(G) ≤ 3. If χ(G) = 3 and G K_2,2,2, then r(S_n,G) has been determined except for some G and some small n. Partial results have been obtained for r(S_n,K_2,2,2) and for r(S_n,G) with χ(G) = 2. In the present paper we investigate r(T_n,G) for non-star trees T_n and χ(G) ≤ 3. Especially, r(T_n,G) is completely evaluated for any non-star tree T_n if χ(G) = 3 where G K_2,2,2, and r(T_n,K_2,2,2) is determined for a class of trees T_n with small maximum degree. In case of χ(G) = 2, r(T_n,G) is investigated for T_n = P_n, the path of order n, and for T_n= B_2,n-2, the special broom of order n obtained by identifying the centre of a star S_3 with an end-vertex of a path P_n-2. Furthermore, the values of r(B_2,n-2,S_m) are determined for all n and m with n ≥ m - 1. As a consequence of this paper, r(F,G) is known for all trees F of order at most five and all connected graphs G of order at most six.
Keywords: Ramsey number, Ramsey goodness, tree, star, path, broom, small graph 
@article{DMGT_2023_43_2_a2,
     author = {Lortz, Roland and Mengersen, Ingrid},
     title = {On the {Ramsey} numbers of non-star trees versus connected graphs of order six},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {331--349},
     year = {2023},
     volume = {43},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a2/}
}
TY  - JOUR
AU  - Lortz, Roland
AU  - Mengersen, Ingrid
TI  - On the Ramsey numbers of non-star trees versus connected graphs of order six
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 331
EP  - 349
VL  - 43
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a2/
LA  - en
ID  - DMGT_2023_43_2_a2
ER  - 
%0 Journal Article
%A Lortz, Roland
%A Mengersen, Ingrid
%T On the Ramsey numbers of non-star trees versus connected graphs of order six
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 331-349
%V 43
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a2/
%G en
%F DMGT_2023_43_2_a2
Lortz, Roland; Mengersen, Ingrid. On the Ramsey numbers of non-star trees versus connected graphs of order six. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 2, pp. 331-349. http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a2/

[1] S.A. Burr, P. Erdős, R.J. Faudree, C.C. Rousseau and R.H. Schelp, Some complete bipartite graph-tree Ramsey numbers, Ann. Discrete Math. 41 (1989) 79–89. https://doi.org/10.1016/S0167-5060(08)70452-7

[2] G. Chartrand, R.J. Gould and A.D. Polimeni, On Ramsey numbers of forests versus nearly complete graphs, J. Graph Theory 4 (1980) 233–239. https://doi.org/10.1002/jgt.3190040211

[3] V. Chvátal, Tree-complete graph Ramsey numbers, J. Graph Theory 1 (1977) 93. https://doi.org/10.1002/jgt.3190010118

[4] V. Chvátal and F. Harary, Generalized Ramsey theory for graphs III:} Small off-diagonal numbers, Pacific J. Math. 41 (1972) 335–345. https://doi.org/10.2140/pjm.1972.41.335

[5] M. Clancy, Some small Ramsey numbers, J. Graph Theory 1 (1977) 89–91. https://doi.org/10.1002/jgt.3190010117

[6] P. Erdős, R.J. Faudree, C.C. Rousseau and R.H. Schelp, The book-tree Ramsey numbers, Scientia, Ser. A: Math. Sci. 1 (1988) 111–117.

[7] R.J. Faudree, C.C. Rousseau and R.H. Schelp, Small order graph-tree Ramsey numbers, Discrete Math. 72 (1988) 119–127. https://doi.org/10.1016/0012-365X(88)90200-2

[8] R.J. Gould and M.S. Jacobson, On the Ramsey number of trees versus graphs with large clique number, J. Graph Theory 7 (1983) 71–78. https://doi.org/10.1002/jgt.3190070109

[9] Y.B. Guo and L. Volkmann, Tree-Ramsey numbers, Australas. J. Combin. 11 (1995) 169–175.

[10] F. Harary, Recent results on generalized Ramsey theory for graphs, in: Graph Theory and Applications, Lecture Notes in Mathematics Vol. 303, Y. Alavi et al. (Ed(s)), (Springer, Berlin 1972) 125–138.

[11] R. Lortz and I. Mengersen, On the Ransey numbers for stars versus connected graphs of order six, Australas. J. Combin. 73 (2019) 1–24.

[12] R. Lortz and I. Mengersen, On the Ramsey numbers r(Sn,K6-3K2), J. Combin. Math. Combin. Comput.}, to appear.

[13] R. Lortz and I. Mengersen, All missing Ramsey numbers for trees versus the four-page book, submitted.

[14] T.D. Parsons, Path-star Ramsey numbers, J. Combin. Theory Ser. B 17 (1974) 51–58. https://doi.org/10.1016/0095-8956(74)90048-3

[15] T.D. Parsons, Ramsey graphs and block designs I}, Trans. Amer. Math. Soc. 209 (1975) 33–44. https://doi.org/10.1090/S0002-9947-1975-0396317-X

[16] A. Pokrovskiy and B. Sudakov, Ramsey goodness of paths, J. Combin. Theory Ser. B 122 (2017) 384–390. https://doi.org/10.1016/j.jctb.2016.06.009

[17] S.P. Radziszowski, Small Ramsey numbers, Electron. J. Combin. (2017) #DS1.15. https://doi.org/10.37236/21

[18] C.C. Rousseau and J. Sheehan, A class of Ramsey problems involving trees, J. Lond. Math. Soc. (2) 18 (1978) 392–396. https://doi.org/10.1112/jlms/s2-18.3.392

[19] Y. Wu, Y. Sun, R. Zhang and S.P. Radziszowski, Ramsey numbers of C4 versus wheels and stars, Graphs Combin. 31 (2015) 2437–2446. https://doi.org/10.1007/s00373-014-1504-3