Three-colour bipartite Ramsey number R_b(G_1,G_2,P_3)

Abstract

For simple bipartite graphs G1, G2, G3, the three-colour bipartite graph Ramsey number Rb(G1,G2,G3) is defined as the least positive integer n such that any 3-edge-colouring of Kn,n assures a monochromatic copy of Gi in the ith colour for some i, i ∈ {1,2,3}. In this paper, we consider the three-colour bipartite Ramsey number Rb(G1,G2,P3). Exact values are determined when G1 = G2 = C4 and when (G1,G2) = (a bistar, a bistar). For integers m,n ≥ 2, a recursive upper bound, Rb(Km,m,Kn,n,P3) ≤ Rb(Km-1,m-1,Kn,n,P3) + Rb(Km,m,Kn-1,n-1,P3) + 3, is given. When G1 and G2 are even cycles, a lower bound is provided. In addition to these results, we have obtained the relations: R(G,K1,n) ≤ Rb(G,K1,n+1) and R(G,H) ≤ Rb(G,H,P3).

Keywords

• bipartite graph ramsey number, $1$-factor, paths, bistars