On size multipartite Ramsey numbers involving complete graphs

Abstract

Given two graphs H and G, the size multipartite Ramsey number mj(H,G) is the smallest natural number t such that an arbitrary coloring of the edges of Kj×t, a complete multipartite graph whose vertex set is partitioned into j parts each of size t, using two colors (red and blue), necessarily contains a red copy of H or a blue copy of G as a subgraph. The notion of size multipartite Ramsey number was introduced by Burger and Vuuren in 2004. This notion extends the idea of the original classical Ramsey number, multipartite Ramsey number and the size Ramsey number. In this paper, we focus on mj(H,G) and find a lower bound for mj(H,G) based on the chromatic number of H and the order of G. Also, for every graph G we obtain a tight lower bound for mj(Km,G) based on m and the maximum degree of G. Furthermore, we determine the order of magnitude of mj(Km,K1,n), for j≥m≥3 and n≥2. Then, we specify the exact values of mj(Km,K1,n) for the cases m=3, m=j and j≡0orm−2(modm−1). © 2025 Elsevier B.V.