Multipartite Ramsey numbers for the union of stars

I Wayan Palton Anuwiksa, Rinovia Simanjuntak, Edy Tri Baskoro

Abstract


Let s and k be positive integers with k ≥ 2 and G1, G2, …, Gk be simple graphs. The set multipartite Ramsey number, denoted by Ms(G1, G2, …, Gk), is the smallest positive integer c such that any k-coloring of the edges of Kc × s contains a monochromatic copy of Gi in color i for some i ∈ {1, 2, …, k}. The size multipartite Ramsey number, denoted by mc(G1, G2, …, Gk), is the smallest positive integer s such that any k-coloring of the edges of Kc × s contains a monochromatic copy of Gi in color i for some i ∈ {1, 2, …, k}. In this paper, we establish some lower and upper bounds, and some exact values of multipartite Ramsey numbers for the union of stars.


Keywords


set multipartite Ramsey number, size multipartite Ramsey number, union of stars

Full Text:

PDF

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

References

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

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

E.L.M. Carmelo and J. Sanches, Multicolor set multipartite Ramsey numbers, Discrete Math., 339 (2016) 2775–2784.

R.L. Graham, B. Rothschild, and J. Spencer, Ramsey Theory. In: Wiley Ser. Discrete Math. Optim., John Wiley and Sons, New Jersey, (2013).

J.W. Grossman, The Ramsey numbers of the union of two stars, Utilitas Math., 16 (1979) 271–279.

A. Lusiani, E.T. Baskoro, and S.W. Saputro, On size tripartite Ramsey numbers of P3 versus mK1, n, AIP. Conf. Proc., 1707 (2016) art. no. 020010.

A. Lusiani, E.T. Baskoro, and S.W. Saputro, On size multipartite ramsey numbers of mK1, n versus P3 or K1, 3, Proc. Jangjeon Math. Soc., 22 (2019) 59–65.

A. Lusiani, E.T. Baskoro, and S.W. Saputro, On size bipartite and tripartite ramsey numbers for the star forest and path on 3 vertices, Journal of Mathematical and Fundamental Sciences, 52 (2020) 1–16.

P.H. Perondi and E.L.M. Carmelo, Set and size multipartite Ramsey numbers for stars, Discrete Appl. Math., 250 (2018) 368–372.

P.H. Perondi and E.L.M. Carmelo, Exact Ramsey number in multipartite graphs arising from Hadamard matrices and strongly regular graphs, Discrete Math., 342 (2019) 2204–2212.

P.H. Perondi and E.L.M. Carmelo, Size multipartite Ramsey numbers for bipartite graphs, Matemática Contemporânea, 46 (2019) 103–111.

S. Sy, E.T. Baskoro, and S. Uttunggadewa, The size multipartite Ramsey numbers for paths, J. Combin. Math. Combin. Comput., 55 (2005) 103–107.


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