Article in press
Authors:
Title:
Bipartite Ramsey number pairs involving cycles
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2023-01-25 , Revised: 2023-10-03 , Accepted: 2023-10-03 , Available online: 2023-11-10 , https://doi.org/10.7151/dmgt.2526
Abstract:
For bipartite graphs $G_1, G_2,\ldots,G_k$, the bipartite Ramsey number
$b(G_1,$ $G_2,\ldots, G_k)$ is the least positive integer $b,$ so that any
coloring of the edges
of $K_{b,b}$ with $k$ colors, will result in a copy of $G_i$ in the $i$th color,
for some $i$. We determine all pairs of positive integers $r$ and $t$, such that
for a sufficiently large positive integer $s$, any $2$-coloring of $K_{r,t}$ has
a monochromatic copy of $C_{2s}$. Let $a$ and $b$ be positive integers with
$a\geq b$. For bipartite graphs $G_1$ and $G_2$, the bipartite Ramsey number
pair $(a,b)$, denoted by $b_p(G_1,G_2)=(a,b)$, is an ordered pair of integers
such that for any blue-red coloring of the edges of $K_{r,t}$, with $r\geq t$,
either a blue copy of $G_1$ exists or a red copy of $G_2$ exists if and only if
$r\geq a$ and $t\geq b$. In [Path-path Ramsey-type numbers for the complete
bipartite graph, J. Combin. Theory Ser. B 19 (1975) 161–173], Faudree and Schelp
showed that $b_{p}(P_{2s},P_{2s})=(2s-1,2s-1)$, for $s\geq 1$. In this paper we
will show that for a sufficiently large positive integer $s$, any 2-coloring of
$K_{2s,2s-1}$ has a monochromatic $C_{2s}$. This will imply that $b_p(C_{2s},
C_{2s})=(2s,2s-1)$, if $s$ is sufficiently large.
Keywords:
bipartite graph, Ramsey, cycle
References:
- M. Bucić, S. Letzter and B. Sudakov, $3$-colour bipartite Ramsey number of cycles and paths, J. Graph Theory 92 (2019) 445–459.
https://doi.org/10.1002/jgt.22463 - G. Chartrand and L. Lesniak, Graphs & Digraphs, Third Edition (Chapman & Hall, London, 1996).
- P. Erdős and R. Rado, A partition calculus in set theory, Bull. Amer. Math. Soc. 62 (1956) 229–489.
https://doi.org/10.1090/S0002-9904-1956-10036-0 - 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 - A. Gyàrfàs, C.C. Rousseau and R.H. Schelp, An extremal problem for paths in bipartite graphs, J. Graph Theory 8 (1984) 83–95.
https://doi.org/10.1002/jgt.3190080109 - J.H. Hattingh and E.J. Joubert, Some multicolor bipartite Ramsey numbers involving cycles and a small number of colors, Discrete Math. 341 (2018) 1325–1330.
https://doi.org/10.1016/j.disc.2018.02.006 - E.J. Joubert, Some generalized bipartite Ramsey numbers involving short cycles, Graphs Combin. 33 (2017) 433–448.
https://doi.org/10.1007/s00373-017-1761-z - L. Shen, Q. Lin and Q. Liu, Bipartite Ramsey numbers for bipartite graphs with small bandwidth, Electron. J. Combin. 25(2) (2018) #P2.16.
https://doi.org/10.37236/7334 - R. Zhang, Y. Sun and Y. Wu, The bipartite Ramsey numbers $b(C_{2m}; C_{2n})$, Int. J. Math. Comput. Sci. 7 (2013) 42–45.
Close