ARTICLE
TITLE

Ramsey Numbers of Trees Versus Odd Cycles

SUMMARY

Burr, Erdos, Faudree, Rousseau and Schelp initiated the study of Ramsey numbers of trees versus odd cycles, proving that R(Tn,Cm)=2n-1R(T_n, C_m) = 2n - 1 for all odd m=3m \ge 3 and n=756m10n \ge 756m^{10}, where TnT_n is a tree with nn vertices and CmC_m is an odd cycle of length mm. They proposed to study the minimum positive integer n0(m)n_0(m) such that this result holds for all n=n0(m)n \ge n_0(m), as a function of mm. In this paper, we show that n0(m)n_0(m) is at most linear. In particular, we prove that R(Tn,Cm)=2n-1R(T_n, C_m) = 2n - 1 for all odd m=3m \ge 3 and n=25mn \ge 25m. Combining this with a result of Faudree, Lawrence, Parsons and Schelp yields n0(m)n_0(m) is bounded between two linear functions, thus identifying n0(m)n_0(m) up to a constant factor.

KEYWORDS

 Articles related

Roland Lortz,Ingrid Mengersen    

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,&n... see more


Chula Janak Jayawardene    

Abstract: Let the star on n vertices, namely K1, n - 1 be denoted by Sn. If every two coloring of the edges of a complete balanced multipartite graph Kj × s there is a copy of Sn in the first color or a copy o... see more


Mark Rowland Budden,Elijah DeJonge    

This paper seeks to develop the multicolor version of star-critical Ramsey numbers, which serve as a measure of the strength of the corresponding Ramsey numbers.  We offer several general theorems, some of which focus on Ramsey-good cases (i.e., cas... see more


Anie Lusiani,Edy Tri Baskoro,Suhadi Wido Saputro    

For simple graphs G and H the size multipartite Ramsey number mj(G,H) is the smallest natural number t such that any arbitrary red-blue coloring on the edges of Kjxt contains a red G or a blue H as a subgraph. We studied the size tripartite Ramsey number... see more


Anie Lusiani,Edy Tri Baskoro,Suhadi Wido Saputro    

Burger and Vuuren defined the size multipartite Ramsey number for a pair of complete, balanced, multipartite graphs mj(Kaxb,Kcxd), for natural numbers a,b,c,d and j, where a,c >= 2, in 2004. They have also determined the necessary and sufficient condi... see more