The connected size Ramsey number for matchings versus small disconnected graphs

Hilda Assiyatun, Budi Rahadjeng, Edy Tri Baskoro


Let F, G,  and H be simple graphs. The notation F → (G, H) means that if all the edges of F are arbitrarily colored by red or blue, then there always exists either a red subgraph G or a blue subgraph H. The size Ramsey number of graph G and H,  denoted by (G, H) is the smallest integer k such that there is a graph F with k edges satisfying F → (G, H). In this research, we will study a modified size Ramsey number, namely the connected size Ramsey number. In this case, we only consider connected graphs F satisfying the above properties. This connected size Ramsey number of G and H is denoted by c(G, H). We will derive an upper bound of c(nK2, H), n ≥ 2 where H is 2Pm or 2K1, t,  and find the exact values of c(nK2, H),  for some fixed n.


connected size Ramsey number, disconnected graph, matching

Full Text:




S.A. Burr, P. Erdo ̋s, R.J. Faudree, C.C. Rousseau, R.H. Schelp, Ramsey minimal graphs for multiple copies, Nederl. Akad. wetensch, Proc. Ser. A81 (1978), 187–195.

P. Erdo ̋s, R.J. Faudree, C.C. Rousseau, R.H. Schelp, The size Ramsey number, Period. Math. Hungar. 9 (1978), 145–161.

P. Erdo ̋s, R.J Faudree, Size Ramsey numbers involving matching, Colloquia Math. Societatis Ja ́nos Bolyai 37 (1981), 247–264.

R.J. Faudree, R.H. Schelp, A survey of results on the size Ramsey number, in Paul Erdo ̋s and his mathematics II (Budapest, 1999), Bolyai Soc. Math. Stud. 11 (2002), 291–309.

Bielak, H., Note size Ramsey number for some regular graphs, Discrete Math. 309 (2012), 6446–6449.

Ben-Eliezer, I., Krivelevich, M., Sudakov, B., The size Ramsey of a directed path, J. Combin. Theory 102 (2012), 743–755.

B. Rahadjeng, E.T. Baskoro, H. Assiyatun, Connected size Ramsey numbers for matchings vs small stars or cycles, Proc. Indian Acad. Sci. Math. Sci. 127 (5) (2017), 787–792.

B. Rahadjeng, E.T. Baskoro, H. Assiyatun, Connected size Ramsey numbers of matchings and stars, AIP Conf. Proc., 1707, 020015 (2016); doi :10.1063/1.4940816.


  • 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