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

Anie Lusiani, Edy Tri Baskoro, Suhadi Wido Saputro

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,n and 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.

Keywords


path; size multipartite Ramsey number; star forest.

Full Text:

PDF

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.




DOI: http://dx.doi.org/10.5614%2Fj.math.fund.sci.2020.52.1.1

Refbacks

  • There are currently no refbacks.


View my Stats

Creative Commons License
This work is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License.

 

Lembaga Penelitian dan Pengabdian kepada Masyarakat (LPPM), Center for Research and Community Services (CRCS) Building, 6th & 7th Floor, Institut Teknologi Bandung, Jalan Ganesha 10, Bandung 40132, Indonesia, Tel. +62-22-86010080, Fax.: +62-22-86010051; E-mail: jmfs@lppm.itb.ac.id