双星图的Ramsey数的上界

An Upper Bound for the Ramsey Numbers of Bistars

对给定的两个图G和H,Ramsey数R(G,H)是最小的正整数N,使得对完全图KN的边任意红/蓝着色,则或者存在红色子图G,或者存在蓝色子图H.双星B(m,n)为直径是3,有两个中心顶点,其顶点度分别为m+1和n+1的树.得到,当n>m时,R(B(m,n))<2n+m+2;当n=m或n=m+1时,R(B(m,n))=2 m+n+2.

For two given graphs Gand H,Ramsey number R（G,H）is the smallest integer Nsuch that any red/blue edgecoloring of KN contains a red copy of Gor 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 nm;and R（B（m,n））=2 m＋n＋2 for n=m or n=m＋1.