The Bipartite Ramsey Numbers b(C2m; C2n)

Given bipartite graphs H1 and H2, the bipartite Ramsey number b(H1;H2) is the smallest integer b such that any subgraph G of the complete bipartite graph Kb,b, either G contains a copy of H1 or its complement relative to Kb,b contains a copy of H2. It is known that b(K2,2;K2,2) = 5, b(K2,3;K2,3) = 9, b(K2,4;K2,4) = 14 and b(K3,3;K3,3) = 17. In this paper we study the case that both H1 and H2 are even cycles, prove that b(C2m;C2n) ≥ m + n - 1 for m = n, and b(C2m;C6) = m + 2 for m ≥ 4.

• Rui Zhang
• Yongqi Sun
• and Yali Wu

• bipartite graph
• Ramsey number
• even cycle

[1] L. W. Beineke and A. J. Schwenk. On a bipartite form of the Ramsey
problem. Proc. 5th British Combin. Conf. 1975, Congressus Number.,
XV: 17-22, 1975.
[2] W. A. Carnielli and E. L. Monte Carmelo. K2,2 − K1,n and K2,n − K2,n bipartite Ramsey numbers. Discrete Math., 223: 83-92, 2000.
[3] R. J. Faudree and R. H. Schelp. Path-path Ramsey-type numbers for the
complete bipartite graphs. J. Combin. Theory Ser. B, 19: 161-173, 1975.
[4] J. H. Hattingh and M. A. Henning. Bipartite Ramsey numbers. Utilitas
Math., 53: 217-230, 1998.
[5] J. H. Hattingh and M. A. Henning. Star-path bipartite Ramsey numbers.
Discrete Math., 185: 255-258, 1998.
[6] R. W. Irving. A bipartite Ramsey problem and the Zarankiewicz numbers.
Discrete Math., 19: 13-26, 1978.
[7] R. Zhang and Y. Q. Sun. The bipartite Ramsey numbers b(C2m;K2,2).
The Elec. J. of Combin., 18: P51, 2011.