Article
Full entry |
PDF
(0.1 MB)
Feedback
PDF
(0.1 MB)
Feedback
Keywords:
size Ramsey number; matching; cycle
size Ramsey number; matching; cycle
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$.
References:
[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. DOI 10.17654/MS102030507 | Zbl 1378.05125
[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. DOI 10.1016/B978-0-444-86893-0.50019-X | MR 0818238 | Zbl 0563.05043
[3] Erdős, P., Faudree, R. J., Rousseau, C. C., Schelp, R. H.: The size Ramsey number. Period. Math. Hung. 9 (1978), 145-161. DOI 10.1007/BF02018930 | MR 0479691 | Zbl 0331.05122
[4] Faudree, R. J., Sheehan, J.: Size Ramsey numbers for small-order graphs. J. Graph Theory 7 (1983), 53-55. DOI 10.1002/jgt.3190070107 | MR 0693020 | Zbl 0505.05043
[5] Ke, X.: The size Ramsey number of trees with bounded degree. Random Struct. Algorithms 4 (1993), 85-97. DOI 10.1002/rsa.3240040106 | MR 1192528 | Zbl 0778.05060
[6] Lortz, R., Mengersen, I.: Size Ramsey results for paths versus stars. Australas. J. Comb. 18 (1998), 3-12. MR 1658352 | Zbl 0914.05053
[7] Perondi, P. H., Carmelo, E. L. Monte: Set and size multipartite Ramsey numbers for stars. Discrete Appl. Math. 250 (2018), 368-372. DOI 10.1016/j.dam.2018.05.016 | MR 3868682 | Zbl 1398.05131
Search
Partner of
