Restricted size Ramsey number for P3 versus cycle

Joanna Cyman, Tomasz Dzido


Let F, G and H be simple graphs. We say F → (G,H) if for every 2-coloring of the edges of F there exists a red copy of G or a blue copy of H in F. The Ramsey number r(G,H) is defined as r(G,H) = min{|V(F)|: F → (G,H)}, while the restricted size Ramsey number r*(G,H) is defined as r*(G,H) = min{|E(F)|: F → (G,H),|V(F)| = r(G,H)}. In this paper we determine previously unknown restricted size Ramsey numbers r*(P3,Cn) for 7 ≤ n ≤ 12. We also give new upper bound r*(P3,Cn) ≤ 2n-2 for n ≥ 10 and n is even.


restricted size Ramsey numbers, path, cycle

Full Text:




C.R.J. Clapham, A. Flockhart, J. Sheehan, Graphs without four-cycles, Journal of Graph Theory, 13 (1989) 29–47.

J. Cyman, T. Dzido, J. Lapinskas, A. Lo, On-line Ramsey Numbers of Paths and Cycles, Electronic Journal of Combinatorics, 22 (2015) #P1.15

P. Erdos, R.J. Faudree, C.C. Rousseau, R.H. Schelp, The size Ramsey number, Periodica Mathematica Hungarica 9(1-2) (1978) 145–161.

P. Erdos, R.J. Faudree, Size Ramsey functions, in: Sets, graphs, and numbers. Colloq. Math. Soc. Janos Bolyai 60 (eds. G. Halasz et al.) North-Holland Publishing Co. Amsterdam 1992, 219–238.

R.J. Faudree, S.L. Lawrence, T.D. Parsons, R.H. Schelp, Path-Cycle Ramsey Numbers, Discrete Mathematics 10 (1974) 269–277.

R.J. Faudree, R.H. Schelp, A survey of results on the size Ramsey number Paul Erdos and his mathematics II (2002) 291–309.

R.J. Faudree, J. Sheehan, Size Ramsey numbers involving stars, Discrete Mathematics 46 (1983) 151–157.

B.D. McKay, A. Piperno, Nauty and traces user’s guide (version 2.6), bdm/nauty/nug26.pdf

D.R. Silaban, E.T. Baskoro, S. Uttunggadewa, On the restricted size Ramsey number, Procedia Computer Science 74 (2015) 21–26.


  • 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