TY - JOUR

T1 - On the size Ramsey number of all cycles versus a path

AU - Bal, Deepak

AU - Schudrich, Ely

N1 - Publisher Copyright:
© 2021 Elsevier B.V.

PY - 2021/5

Y1 - 2021/5

N2 - We say G→(C,Pn) if G−E(F) contains an n-vertex path Pn for any spanning forest F⊂G. The size Ramsey number Rˆ(C,Pn) is the smallest integer m such that there exists a graph G with m edges for which G→(C,Pn). Dudek, Khoeini and Prałat proved that for sufficiently large n, 2.0036n≤Rˆ(C,Pn)≤31n. In this note, we improve both the lower and upper bounds to 2.066n≤Rˆ(C,Pn)≤5.25n+O(1). Our construction for the upper bound is completely different than the one considered by Dudek, Khoeini and Prałat. We also have a computer assisted proof of the upper bound [Figure presented].

AB - We say G→(C,Pn) if G−E(F) contains an n-vertex path Pn for any spanning forest F⊂G. The size Ramsey number Rˆ(C,Pn) is the smallest integer m such that there exists a graph G with m edges for which G→(C,Pn). Dudek, Khoeini and Prałat proved that for sufficiently large n, 2.0036n≤Rˆ(C,Pn)≤31n. In this note, we improve both the lower and upper bounds to 2.066n≤Rˆ(C,Pn)≤5.25n+O(1). Our construction for the upper bound is completely different than the one considered by Dudek, Khoeini and Prałat. We also have a computer assisted proof of the upper bound [Figure presented].

KW - Ramsey Theory

KW - Size Ramsey

KW - Sparse Graphs

UR - http://www.scopus.com/inward/record.url?scp=85100607156&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2021.112322

DO - 10.1016/j.disc.2021.112322

M3 - Article

AN - SCOPUS:85100607156

VL - 344

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 5

M1 - 112322

ER -