| 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 |
| . |
