The Bipartite Ramsey Numbers b(C2m; C2n)

Authors: Rui Zhang, Yongqi Sun, and Yali Wu

Abstract:

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.

Keywords: bipartite graph, Ramsey number, even cycle

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1335404

References:

[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.