An Upper Bound for the Ramsey Numbers of Bistars

Abstract:

For two given graphs G and H, Ramsey number R(G,H) is the smallest integer N such that any red/blue edgecoloring of KN contains a red copy of G or a blue copy of H. Let a bistar B(m,n) be a tree of diameter three with two central vertices of degree m+1 and n+1, respectively. It is shown that R(B(m,n))<2n+m+2 for n>m; and R(B(m,n))=2m+n+2 for n=m or n=m+1. Key words： Ramsey number; tree; bistar