DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2023): 0.5

5-year Journal Impact Factor (2023): 0.6

CiteScore (2023): 2.2

SNIP (2023): 0.681

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

Y. Rowshan

Yaser Rowshan

PhD

email: y.rowshan@iasbs.ac.ir

Title:

The $m$-bipartite Ramsey number $BR_m(H_1,H_2)$

PDF

Source:

Discussiones Mathematicae Graph Theory 44(3) (2024) 893-911

Received: 2022-02-10 , Revised: 2022-10-17 , Accepted: 2022-10-18 , Available online: 2022-11-26 , https://doi.org/10.7151/dmgt.2477

Abstract:

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\geq 1$, such that for every $(G^1, G^2)$ coloring of the complete bipartite graph $K_{b,b}$, results in either $H_1\subseteq G^1$ or $H_2\subseteq 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\geq m)$ such that every subgraph $G$ of $K_{m,n}$ results in $H_1\subseteq G$ or $H_2\subseteq \overline{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\geq 2$.

Keywords:

Ramsey numbers, bipartite Ramsey numbers, complete graphs, $m$-bipartite Ramsey number

References:

  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(C_8,C_{2n})$ (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 $R_b (G_1, G_2, P_3)$, 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 $nK_2$ versus path–path and cycle, Mathematics 9 (2021) 764.
    https://doi.org/10.3390/math9070764
Close