Geodesic
The $m$-bipartite Ramsey number $BR_m(H_1,H_2)$
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 893-911 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

In a (G^1,G^2) coloring of a graph G, every edge of G is in G^1 or G^2. For two bipartite graphs H_1 and H_2, the bipartite Ramsey number BR(H_1, H_2) is the least integer b≥ 1, such that for every (G^1, G^2) coloring of the complete bipartite graph K_b,b, results in either H_1⊆ G^1 or H_2⊆ G^2. As another view, for bipartite graphs H_1 and H_2 and a positive integer m, the m-bipartite Ramsey number BR_m(H_1, H_2) of H_1 and H_2 is the least integer n (n≥ m) such that every subgraph G of K_m,n results in H_1⊆ G or H_2⊆G. The size of m-bipartite Ramsey number BR_m(K_2,2, K_2,2), the size of m-bipartite Ramsey number BR_m(K_2,2, K_3,3) and the size of m-bipartite Ramsey number BR_m(K_3,3, K_3,3) have been computed in several articles up to now. In this paper we determine the exact value of BR_m(K_2,2, K_4,4) for each m≥ 2.
Keywords: Ramsey numbers, bipartite Ramsey numbers, complete graphs, $m$-bipartite Ramsey number 
@article{DMGT_2024_44_3_a4,
     author = {Rowshan, Yaser},
     title = {The $m$-bipartite {Ramsey} number $BR_m(H_1,H_2)$},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {893--911},
     year = {2024},
     volume = {44},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a4/}
}
TY  - JOUR
AU  - Rowshan, Yaser
TI  - The $m$-bipartite Ramsey number $BR_m(H_1,H_2)$
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 893
EP  - 911
VL  - 44
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a4/
LA  - en
ID  - DMGT_2024_44_3_a4
ER  - 
%0 Journal Article
%A Rowshan, Yaser
%T The $m$-bipartite Ramsey number $BR_m(H_1,H_2)$
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 893-911
%V 44
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a4/
%G en
%F DMGT_2024_44_3_a4
Rowshan, Yaser. The $m$-bipartite Ramsey number $BR_m(H_1,H_2)$. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 893-911. http://geodesic.mathdoc.fr/item/DMGT_2024_44_3_a4/

[1] L.W. Beineke and A.J. Schwenk, On a bipartite form of the Ramsey problem, in: Proc. Fifth British Combinatorial Conference, Aberdeen, 1975}, Util. Math. 15 (1976) 17–22.

[2] Z. Bi, G. Chartrand and P. Zhang, Another view of bipartite Ramsey numbers, Discuss. Math. Graph Theory 38 (2018) 587–605. https://doi.org/10.7151/dmgt.2034

[3] M. Bucić, S. Letzter and B. Sudakov, Multicolour bipartite Ramsey number of paths, Electron. J. Combin. 26 (2019) #P3.60. https://doi.org/10.37236/8458

[4] M. Bucić, S. Letzter and B. Sudakov, 3-color bipartite Ramsey number of cycles and paths, J. Graph Theory 92 (2019) 445–459. https://doi.org/10.1002/jgt.22463

[5] G. Chartrand and P. Zhang, New directions in Ramsey theory, Discrete Math. Lett. 6 (2021) 84–96. https://doi.org/10.47443/dml.2021.s110

[6] A.F. Collins, Bipartite Ramsey Numbers and Zarankiewicz Numbers, M.Sc. Thesis (Rochester Institute of Technology, 2015).

[7] A.F. Collins, A.W.N. Riasanovsky, J.C. Wallace and S.P. Radziszowski, Zarankiewicz numbers and bipartite Ramsey numbers, J. Algorithms Comput. 47 (2016) 63–78. https://doi.org/10.22059/jac.2016.7943

[8] D. Day, W. Goddard, M.A. Henning, and H.C. Swart, Multipartite Ramsey numbers, Ars Combin. 58 (2001) 23–32.

[9] J. Dybizbański, T. Dzido and S. Radziszowski, On some Zarankiewicz numbers and bipartite Ramsey Numbers for quadrilateral, Ars Combin. 119 (2016) 275–287.

[10] R.J. Faudree and R.H. Schelp, Path-path Ramsey-type numbers for the complete bipartite graph, J. Combin. Theory Ser. B 19 (1975) 161–173. https://doi.org/10.1016/0095-8956(75)90081-7

[11] M. Gholami and Y. Rowshan, The bipartite Ramsey numbers BR(C8,C2n) (2021). arXiv: 2108.02630

[12] W. Goddard, M.A. Henning and O.R. Oellermann, Bipartite Ramsey numbers and Zarankiewicz numbers, Discrete Math. 219 (2000) 85–95. https://doi.org/10.1016/S0012-365X(99)00370-2

[13] A. Gyárfás and J. Lehel, A Ramsey-type problem in directed and bipartite graphs, Period. Math. Hungar. 3 (1973) 299–304. https://doi.org/10.1007/BF02018597

[14] I. Hatala, T. Héger, and S. Mattheus, New values for the bipartite Ramsey number of the four-cycle versus stars, Discrete Math. 344 (2021) 112320. https://doi.org/10.1016/j.disc.2021.112320

[15] J. Hattingh and M. Henning, Bipartite Ramsey theory, Util. Math. 53 (1998) 217–230.

[16] J.H. Hattingh and M.A. Henning, Star-path bipartite Ramsey numbers, Discrete Math. 185 (1998) 255–258. https://doi.org/10.1016/S0012-365X(97)00205-7

[17] R. Lakshmi and D. Sindhu, Three-colour bipartite Ramsey number Rb (G1, G2, P3), Electron. J. Graph Theory Appl. (EJGTA) 8 (2020) 195–204. https://doi.org/10.5614/ejgta.2020.8.1.14

[18] V. Longani, Some bipartite Ramsey numbers, Southeast Asian Bull. Math. 26 (2003) 583–592. https://doi.org/10.1007/s100120200062

[19] G. Raeisi, Star-path and star-stripe bipartite Ramsey numbers in multicoloring, Trans. Comb. 4 (2015) 37–42. https://doi.org/https://doi.org/10.22108/toc.2015.7275

[20] Y. Rowshan and M. Gholami, Another view of bipartite Ramsey numbers, (2022). https://doi.org/10.48550/arXiv.2201.12844

[21] Y. Rowshan, M. Gholami and S. Shateyi, A proof of a conjecture on bipartite Ramsey numbers B(2, 2, 3), Mathematics 10 (2022) 701. https://doi.org/10.3390/math10050701

[22] Y. Rowshan, M. Gholami and S. Shateyi, The size, multipartite Ramsey numbers for nK2 versus path–path and cycle, Mathematics 9 (2021) 764. https://doi.org/10.3390/math9070764