Some Bistar Bipartite Ramsey Numbers

摘要

For bipartite graphs G_1, G_2,..., G_k, the bipartite Ramsey number b(G_1, G_2,..., G_k) is the least positive integer b so that any colouring of the edges of K_(b,b) with k colours will result in a copy of G_i in the ith colour for some i. A tree of diameter three is called a bistar, and will be denoted by B(s, t), where s ≥ 2 and t ≥ 2 are the degrees of the two support vertices. In this paper we will obtain some exact values for b(B(s, t), B(s, t)) and b(B(s, s), B(s, s)). Furtermore, we will show that if k colours are used, with k ≥ 2 and s ≥ 2, then b_k (B(s, s)) ≤ [k(s - 1) + √(s - 1)~2(k~2 - k) - k(2s - 4)]. Finally,we showthat for s ≥ 3 and k ≥ 2, the Ramsey number r_k (B(s, s)) ≤ [2k(s-1)+ 1/2+ 1/2√(4k(s - 1) + 1)~2 - 8k(2s~2 - s - 2)].