一些扫帚图的Ramsey数

Ramsey Number for Some Brooms

给定图G,Ramsey数R(G)是最小的正整数N,满足对完全图K_N的边任意红蓝着色,则或者存在红色子图G或者存在蓝色子图G.扫帚图B_(k,m)是将星图K_(1,k)的中心点与路Pm的一个端点黏成一个点得到的树图.由此得到,当k为大于1的正整数时,R(B_(k,2k-1))=4k-2且R(B_(k,4))=2k+3.

For a given graph G,Ramsey number R（G）is the smallest integer N such that any red/blue edge-coloring of K_N contains a red copy or a blue copy of G.Let broom Bk,m be a tree obtained by identifying the central vertex of a star K_（1,k） with an end-vertex of Pm.It is proven that R（B_（k,2k-1））=4k-2and R（B_（k,4））=2k＋3for integer k1.