A strict upper bound for size multipartite Ramsey numbers of paths versus stars

Chula Jayawardene, Lilanthi Samarasekara


Let $P_n$ represent the path of size $n$. Let $K_{1,m-1}$ represent a star of size $m$ and be denoted by $S_{m}$. Given a two coloring of the edges of a complete graph $K_{j \times s}$ we say that $K_{j \times s}\rightarrow (P_n,S_{m+1})$ if there is a copy of $P_n$ in the first color or a copy of $S_{m+1}$ in the second color. The size Ramsey multipartite number $m_j(P_n, S_{m+1})$ is the smallest natural number $s$ such that $K_{j \times s}\rightarrow (P_n,S_{m+1})$. Given $j,n,m$ if $s=\left\lceil \dfrac{n+m-1-k}{j-1} \right\rceil$, in this paper, we show that the size Ramsey numbers $m_j(P_n,S_{m+1})$ is bounded above by $s$ for $k=\left\lceil \dfrac{n-1}{j} \right\rceil$. Given $j\ge 3$ and $s$, we will obtain an infinite class $(n,m)$ that achieves this upper bound $s$. In the later part of the paper, will also investigate necessary and sufficient conditions needed for the upper bound to hold.


Graph theory, Ramsey theory

Full Text:



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.

P. Erdos , J. Faudree , C. C. Rousseau and Sheehan Journal The size Ramsey number, Period Math. Hungary (1978), 145--161.

Radziszowski S.P., Small Ramsey numbers, Electronic Journal of Combinatorics, (rev 14) (2004), DS1.

C. C. Rousseau and J. Sheehan, On Ramsey numbers for books, Journal of Graph Theory, 2 (1978), 77--87.

Syafrizal Sy, E.T. Baskoro and S. Uttunggadewa, The size multipartite Ramsey number for paths, Journal Combin. Math. Combin. Comput., 55 (2005), 103--107.

Syafrizal Sy, E.T.Baskoro and S. Uttunggadewa, The size multipartite Ramsey numbers for small paths versus other graphs, Far East Journal Appl. Math. 28 (1) (2007), 131--138.

Syafrizal Sy, E.T.Baskoro, S. Uttunggadewa and H. Assiyatun, Path-path size multipartite Ramsey numbers, Journal Combin. Math. Combin. Comput. 71 (2009), 265--271.

Syafrizal Sy, and E.T. Baskoro, Lower bounds of the size multipartite Ramsey numbers, The 5th Mathematics, AIP Conf. Proc. 1450 (2012), 259--261 .

Syafrizal Sy, On size multipartite Ramsey numbers for paths versus cycles of three or four vertices, Far East Journal Appl. Math. 44 (2010), 109--116.

Syafrizal Sy, On the size multipartite Ramsey numbers for small path versus cocktail party graphs, Far East Journal Appl. Math, 55 (1) (2011), 53--60.

DOI: http://dx.doi.org/10.19184/ijc.2017.1.2.2


  • There are currently no refbacks.

ISSN: 2541-2205

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

View IJC Stats