Previous |  Up |  Next

Article

Title: A note on the size Ramsey numbers for matchings versus cycles (English)
Author: Baskoro, Edy Tri
Author: Vetrík, Tomáš
Language: English
Journal: Mathematica Bohemica
ISSN: 0862-7959 (print)
ISSN: 2464-7136 (online)
Volume: 146
Issue: 2
Year: 2021
Pages: 229-234
Summary lang: English
.
Category: math
.
Summary: For graphs $G$, $F_1$, $F_2$, we write $G \rightarrow (F_1, F_2)$ if for every red-blue colouring of the edge set of $G$ we have a red copy of $F_1$ or a blue copy of $F_2$ in $G$. The size Ramsey number $\hat {r}(F_1, F_2)$ is the minimum number of edges of a graph $G$ such that $G \rightarrow (F_1, F_2)$. Erdős and Faudree proved that for the cycle $C_n$ of length $n$ and for $t \ge 2$ matchings $tK_2$, the size Ramsey number $\hat {r} (tK_2, C_n) < n + (4t+3) \sqrt {n}$. We improve their upper bound for $t = 2$ and $t=3$ by showing that $\hat {r} (2K_2, C_n) \le n + 2 \sqrt {3n} + 9$ for $n \ge 12$ and $\hat {r} (3K_2, C_n) < n + 6 \sqrt {n} + 9$ for $n \ge 25$. (English)
Keyword: size Ramsey number
Keyword: matching
Keyword: cycle
MSC: 05C35
MSC: 05C55
DOI: 10.21136/MB.2020.0174-18
.
Date available: 2021-05-20T13:56:06Z
Last updated: 2021-06-07
Stable URL: http://hdl.handle.net/10338.dmlcz/148934
.
Reference: [1] Effendi, Ginting, B., Surahmat, Dafik, Sy, S.: The size multipartite Ramsey numbers of large paths versus small graph.Far East J. Math. Sci. (FJMS) 102 (2017), 507-514. Zbl 1378.05125, 10.17654/MS102030507
Reference: [2] Erdős, P., Faudree, R. J.: Size Ramsey numbers involving matchings.Finite and Infinite Sets. Vol. I, II (Eger, 1981) Colloquia Mathematica Societatis János Bolyai 37. János Bolyai Mathematical Society, Budapest; North-Holland, Amsterdam (1984), 247-264 A. Hajnal et al. Zbl 0563.05043, MR 0818238, 10.1016/B978-0-444-86893-0.50019-X
Reference: [3] Erdős, P., Faudree, R. J., Rousseau, C. C., Schelp, R. H.: The size Ramsey number.Period. Math. Hung. 9 (1978), 145-161. Zbl 0331.05122, MR 0479691, 10.1007/BF02018930
Reference: [4] Faudree, R. J., Sheehan, J.: Size Ramsey numbers for small-order graphs.J. Graph Theory 7 (1983), 53-55. Zbl 0505.05043, MR 0693020, 10.1002/jgt.3190070107
Reference: [5] Ke, X.: The size Ramsey number of trees with bounded degree.Random Struct. Algorithms 4 (1993), 85-97. Zbl 0778.05060, MR 1192528, 10.1002/rsa.3240040106
Reference: [6] Lortz, R., Mengersen, I.: Size Ramsey results for paths versus stars.Australas. J. Comb. 18 (1998), 3-12. Zbl 0914.05053, MR 1658352
Reference: [7] Perondi, P. H., Carmelo, E. L. Monte: Set and size multipartite Ramsey numbers for stars.Discrete Appl. Math. 250 (2018), 368-372. Zbl 1398.05131, MR 3868682, 10.1016/j.dam.2018.05.016
.

Files

Files Size Format View
MathBohem_146-2021-2_9.pdf 190.4Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo