All missing Ramsey numbers for trees versus the four-page book

Roland Lortz, Ingrid Mengersen

Abstract


For the Ramsey number r(Tn, Bm), where Tn denotes a tree of order n and Bm denotes the m-page book K2 + bar(K)m, it is known that r(Tn, Bm)=2n − 1 if n ≥ 3m − 3. In case of n < 3m − 3, r(Tn, Bm) has not been completely evaluated except for m ≤ 3. Here we determine the missing values of r(Tn, B4). Our results close one gap in the table of the Ramsey numbers r(Tn, G) for all trees Tn and all connected graphs G of order six.


Keywords


Ramsey number, tree, book, small graph

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2021.9.2.10

References

V. Chvatal and F. Harary, Generalized Ramsey theory for graphs III: Small off-diagonal numbers, Pacific J. Math. 41 (1972), 335–345.

M. Clancy, Some small Ramsey numbers, J. Graph Theory 1 (1977), 89–91.

P. Erdos, R.J. Faudree, C.C. Rousseau, and R.H. Schelp, The book-tree Ramsey numbers, Sci. Ser. A Math. Sci. (N.S) 1 (1988), 111–117.

G. Hua, S. Hongxue and L. Xiangyang, Ramsey numbers r(K1,4, G) for all three-partite graphs G of order six, J. Southeast Univ. (English Ed.) 20 (2004), 378–380.

G.R.T. Hendry, Ramsey numbers for graphs with five vertices, J. Graph Theory 13 (1989), 245–248.

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

R. Lortz and I. Mengersen, On the Ramsey numbers for non-star trees versus connected graphs of order six, Discuss. Math. Graph Theory, to appear.

C.C. Rousseau and J. Sheehan, A class of Ramsey problems involving trees, J. London Math. Soc.(2) 18 (1978), 392–396.

L. Zhang, K. Chen, and D. Zhu, Some tree-book Ramsey numbers, Ars Combin. 130 (2017), 97–102.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats