On Size Bipartite and Tripartite Ramsey Numbers for The Star Forest and Path on 3 Vertices

Authors

  • Anie Lusiani Politeknik Negeri Bandung, Jalan Gegerkalong Hilir, Ciwaruga, Kabupaten Bandung Barat 40559 Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Jalan Ganesha 10, Bandung 40132
  • Edy Tri Baskoro Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Jalan Ganesha 10, Bandung 40132
  • Suhadi Wido Saputro Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Jalan Ganesha 10, Bandung 40132

DOI:

https://doi.org/10.5614/j.math.fund.sci.2020.52.1.1

Keywords:

path, size multipartite Ramsey number, star forest.

Abstract

For simple graphs G and H the size multipartite Ramsey number mj(G,H) is the smallest natural number t such that any arbitrary red-blue coloring on the edges of Kjxt contains a red G or a blue H as a subgraph. We studied the size tripartite Ramsey numbers m3(G,H)where G=mK1,nand H=P3. In this paper, we generalize this result. We determine m3(G,H) where G is a star forest, namely a disjoint union of heterogeneous stars, and H=P3. Moreover, we also determine m2(G,H) for this pair of graphs G and H.

References

Parsons, T., Path-star Ramsey Numbers, J. Combin. Theory, Ser. B, 17, pp. 51-58, 1974.

Burr, S.A. & Roberts, J.A., On Ramsey Numbers for Stars, Utilitas Math., 4, pp. 217-220, 1973.

Hattingh, J.H. & Henning, M.A., Star-path Bipartite Ramsey Numbers, Discrete Math. 185, pp. 255-258, 1998.

Burger, A. P. & van Vuuren, J.H., Ramsey Numbers in Complete Balanced Multipartite Graphs. Part II: Size Numbers, Discrete Math., 283, pp. 45-49, 2004.

Syafrizal, Sy., Baskoro, E.T. & Uttunggadewa, S., The Size Multipartite Ramsey Numbers for Paths, J. Combin. Math. Combin. Comput. 55, pp. 103-107, 2005.

Syafrizal, Sy., On Size Multipartite Ramsey Numbers for Paths Versus Cycles of Three or Four Vertices, Far East J. Appl. Math. 44(2), pp. 109-116, 2010.

Syafrizal, Sy., Baskoro, E.T. & Uttunggadewa, S., The Size Multipartite Ramsey Numbers for Small Paths Versus other Graphs, Far East J. Appl. Math. 28(1), pp. 131-138, 2007.

Surahmat & Syafrizal, Sy. , Star-path Size Multipartite Ramsey Numbers, Applied Math. Sciences (Bulgaria), 8(75), pp. 3733-3736, 2014.

Lusiani, A., Syafrizal, S., Baskoro, E.T. & Jayawardene, C., On Size Multipartite Ramsey Numbers for Stars versus Cycles, Procedia Comput. Sci., 74, pp. 27-31, 2015.

Lusiani, A., Baskoro, E.T. & Saputro, S.W., On Size Tripartite Ramsey Numbers of P3 versus mK1,n, AIP. Conf. Proc. 1707, 020010, 2016. DOI:10.1063/1.4940811

Lusiani, A., Baskoro, E.T. & Saputro, S.W., On Size Multipartite Ramsey Numbers for Stars Versus Paths and Cycles, Electron. J. Graph Theory Appl. 5(1), pp. 43-50, 2017.

Jayawardene, C. & Samarasekara, L., The Size Multipartite Ramsey Numbers for C3 versus All Graphs up to 4 Vertices, J.Natn.Sci. Foundation Sri Lanka 45(1), pp. 67-72, 2017, DOI:10.4038/jnsfsr. v45i1.8039

Chartrand, G., Lesniak, L & Zhang, P., Graphs and Digraphs, CRC Press, 2016.

Christou, M., Iliopoulos, C.S. & Miller, M., Bipartite Ramsey Numbers Involving Stars, Stripes and Trees, Electron. J. Graph Theory Appl. 1(2), pp. 89-99, 2013.

Downloads

Published

2020-04-29

Issue

Section

Articles