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

R Lakshmi, D.G. Sindhu

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

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2020.8.1.14

References

R. Balakrishnan and K. Ranganathan, A Textbook of Graph Theory, Second Edition, Springer, New York, 2012.

L.W. Beineke and A.J. Schwenk, On a bipartite form of the Ramsey problem, Proc. 5th British Combin. Conf. 1975, Congressus Numer. XV, (1975), 17-22.

A.P. Burger and J.H. van Vuuren, Ramsey numbers in complete balanced multipartite graphs. Part I: Set numbers, Discrete Math., 283 (2004), 37-43.

A.P. Burger and J.H. van Vuuren, Ramsey numbers in complete balanced multipartite graphs. Part II: Size numbers, Discrete Math., 283 (2004), 45-49.

W.A. Carnielli and E.L. Monte Carmelo, K_{2,2} − K_{1,n} and K_{2,n} − K_{2,n} bipartite Ramsey numbers, Discrete Math., 223 (2000), 83-92.

M. Christou, C.S. Iliopoulos and M. Miller, Bipartite Ramsey numbers involving stars, stripes and trees, Electron. J. Graph Theory Appl., 1(2) (2013), 89-99.

G. Raeisi, Star-path and star-stripe bipartite Ramsey numbers in multicoloring, Transactions on Combinatorics, Vol. 4, No. 3 (2015), 37-42.

A. Gon¸calves and E.L. Monte Carmelo, Some geometric structures and bounds for Ramsey numbers, Discrete Math., 280 (2004), 29-38.

R.L. Graham, B.L. Rothschild and J.H. Spencer, Ramsey Theory, Second Edition, John Wiley and Sons, New York, 1990.

J.H. Hattingh and M.A. Henning, Bipartite Ramsey theory, Utilitas Math., 53 (1998), 217-230.

J.H. Hattingh and M.A. Henning, Star-path bipartite Ramsey numbers, Discrete Math., 185 (1998), 225-258.

J.H. Hattingh and E.J. Joubert, Some bistar bipartite Ramsey numbers, Graphs and Combin., 30 (5) (2014), 1175-1181.

R.W. Irving, A bipartite Ramsey problem and the Zarankiewicz numbers, Glasgow Math. J., 19 (1978), 13-26.

R. Zhang and Y.Q. Sun, The bipartite Ramsey numbers b(C2m;K2,2), The Electron. J. Combin., 18 (2011), P. 51.

R. Zhang, Y.Q. Sun and Y.Wu, The bipartite Ramsey numbers b(C2m;C2n), International Journal of Mathematical, Computational, Physical, Electrical and Computer Engineering, 7(1) (2013), 152-155.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats