1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

On the Ramsey Numbers of Non-Star Trees Versus Connected Graphs of Order Six

Published Online: 24 Nov 2020
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 22 Jun 2019
Accepted: 28 Sep 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

This paper completes our studies on the Ramsey number r(Tn, G) for trees Tn of order n and connected graphs G of order six. If χ(G) ≥ 4, then the values of r(Tn, G) are already known for any tree Tn. Moreover, r(Sn, G), where Sn denotes the star of order n, has been investigated in case of χ(G) ≤ 3. If χ(G) = 3 and GK2,2,2, then r(Sn, G) has been determined except for some G and some small n. Partial results have been obtained for r(Sn, K2,2,2) and for r(Sn, G) with χ(G) = 2. In the present paper we investigate r(Tn, G) for non-star trees Tn and χ(G) ≤ 3. Especially, r(Tn, G) is completely evaluated for any non-star tree Tn if χ(G) = 3 where GK2,2,2, and r(Tn, K2,2,2) is determined for a class of trees Tn with small maximum degree. In case of χ(G) = 2, r(Tn, G) is investigated for Tn = Pn, the path of order n, and for Tn = B2,n−2, the special broom of order n obtained by identifying the centre of a star S3 with an end-vertex of a path Pn−2. Furthermore, the values of r(B2,n−2, Sm) are determined for all n and m with nm − 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

MSC 2010

[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. doi:10.1016/S0167-5060(08)70452-710.1016/S0167-5060(08)70452-7Search in Google Scholar

[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. doi:10.1002/jgt.319004021110.1002/jgt.3190040211Search in Google Scholar

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

[4] V. Chvátal and F. Harary, Generalized Ramsey theory for graphs III: Small o -diagonal numbers, Pacific J. Math. 41 (1972) 335–345. doi:10.2140/pjm.1972.41.33510.2140/pjm.1972.41.335Search in Google Scholar

[5] M. Clancy, Some small Ramsey numbers, J. Graph Theory 1 (1977) 89–91. doi:10.1002/jgt.319001011710.1002/jgt.3190010117Search in Google Scholar

[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.Search in Google Scholar

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

[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. doi:10.1002/jgt.319007010910.1002/jgt.3190070109Search in Google Scholar

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

[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.10.1007/BFb0067364Search in Google Scholar

[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.Search in Google Scholar

[12] R. Lortz and I. Mengersen, On the Ramsey numbers r(Sn, K6 − 3K2), J. Combin. Math. Combin. Comput., to appear.Search in Google Scholar

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

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

[15] T.D. Parsons, Ramsey graphs and block designs I, Trans. Amer. Math. Soc. 209 (1975) 33–44. doi:10.1090/S0002-9947-1975-0396317-X10.1090/S0002-9947-1975-0396317-XSearch in Google Scholar

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

[17] S.P. Radziszowski, Small Ramsey numbers, Electron. J. Combin. (2017) #DS1.15. doi:10.37236/2110.37236/21Search in Google Scholar

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

[19] Y. Wu, Y. Sun, R. Zhang and S.P. Radziszowski, Ramsey numbers of C4versus wheels and stars, Graphs Combin. 31 (2015) 2437–2446. doi:10.1007/s00373-014-1504-310.1007/s00373-014-1504-3Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo