Article in press
Authors:
Qingquan Zhou
School of Mathematics and Statistics,
Hainan University
Haikou, Hainan 570228, P. R. China
email: puppy@hainanu.edu.cn
Zhidan Luo
School of Mathematics and Statistics,
Hainan University
Haikou, Hainan 570228, P. R. China
email: luodan@hainanu.edu.cn
Title:
Monochromatic stars and matchings in complete multipartite graphs
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2025-03-17 , Revised: 2025-07-17 , Accepted: 2025-07-18 , Available online: 2025-08-29 , https://doi.org/10.7151/dmgt.2598
Abstract:
For graphs $G_{1},\dots, G_{l}$ and $G$, let $G\rightarrow(G_{1}, \dots, G_{l})$
denote that any $l$-coloring of $E(G)$ yields a monochromatic $G_{i}$ in color
$i$ for some $i\in [l]$. Let $K_{1,n}$ be the star of order $n+1$, $mK_{2}$ be
the matching of size $m$, and $K_{N_{1}, \dots, N_{k}}$ be the complete
$k$-partite graph whose partite sets have sizes $N_{1}, \dots, N_{k- 1}$ and
$N_{k}$, respectively. In this paper, we prove that if $\sum_{l= 1}^{k} N_{l}
\geq \max\{2n+ m- 2, 2m\}$ and $\sum_{l= 1}^{k} N_{l}- N_{c}\geq m$ for each
$c\in [k]$, then $K_{N_{1}, \dots, N_{k}}\rightarrow(K_{1, n}, mK_{2})$.
Furthermore, we extend it to multicolors.
Keywords:
bipartite Ramsey numbers, set and size multipartite Ramsey numbers, multipartite graphs
References:
- 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.
https://doi.org/10.1016/j.disc.2004.02.004 - 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.
https://doi.org/10.1016/j.disc.2004.02.003 - S.A. Burr and J. Roberts, On Ramsey numbers for stars, Util. Math. 4 (1973) 217–220.
- E.J. Cockayne and P.J. Lorimer, On Ramsey graph numbers for stars and stripes, Canad. Math. Bull. 18 (1975) 31–34.
https://doi.org/10.4153/CMB-1975-005-0 - E.J. Cockayne and P.J. Lorimer, The Ramsey number for stripes, J. Aust. Math. Soc. 19 (1975) 252–256.
https://doi.org/10.1017/S1446788700029554 - 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 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 - F. Harary, Recent results on generalized Ramsey theory for graphs, in: Graph Theory and Applications, Y. Alavi, D.R. Lick and A.T. White (Ed(s)), Lecture Notes in Math. 303, (Springer, Berlin, Heidelberg, 1972) 125–138.
https://doi.org/10.1007/BFb0067364 - C. Jayawardene and L. Samarasekara, Size multipartite Ramsey numbers for stripes versus stripes, Ars Combin. 129 (2016) 357–366.
- G.R. Omidi, G. Raeisi and Z. Rahimi, Stars versus stripes Ramsey numbers, European J. Combin. 67 (2018) 268–274.
https://doi.org/10.1016/j.ejc.2017.08.009 - P.H. Perondi and E.L. Monte Carmelo, Set and size multipartite Ramsey numbers for stars, Discrete Appl. Math. 250 (2018) 368–372.
https://doi.org/10.1016/j.dam.2018.05.016 - G. Raeisi, Star-path and star-stripe bipartite Ramsey numbers in multicoloring, Trans. Comb. 4 (2015) 37–42.
https://doi.org/10.22108/toc.2015.7275
Close