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
SN - 0012-365X
VL - 344
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 5
M1 - 112322
ER -