Volume 7, Issue 3 (Vol.7, No.3, 2021)
mmr 2021, 7(3): 485-494 |
Back to browse issues page
1- Isfahan University of Technology , rjavadi@cc.iut.ac.ir
2- Isfahan University of Technology
2- Isfahan University of Technology
Abstract: (1073 Views)
The size-Ramsey number of a graph 
denoted by is the smallest integer 
such that there is a graph with edges with this property that for any coloring of the edges of 
with
colors, contains a monochromatic copy of
. The investigation of the size-Ramsey numbers of graphs was initiated by Erdős‚ Faudree‚ Rousseau and Schelp in 1978. Since then, Size-Ramsey numbers have been studied with particular focus on the case of trees and bounded degree graphs.
Addressing a question posed by Erdős‚ Beck [2] proved that the size-Ramsey number of the path
is linear in 
by means of a probabilistic construction. In fact, Beck’s proof implies that and this upper bound was improved several times. Currently‚ the best known upper bound is due to Dudek and Prałat [4] which proved that . On the other hand‚ the first nontrivial lower bound for was provided by Beck and his result was subsequently improved by Dudek and Prałat [3] who showed that. The strongest known lower bound was proved recently by Bal and DeBiasio [1].
./files/site1/files/%D8%AC%D9%88%D8%A7%D8%AF%DB%8C_%D9%85%DB%8C%D8%B1%D8%B9%D9%84%D8%A7%DB%8C%DB%8C.pdf
denoted by is the smallest integer such that there is a graph with edges with this property that for any coloring of the edges of with colors, contains a monochromatic copy of. The investigation of the size-Ramsey numbers of graphs was initiated by Erdős‚ Faudree‚ Rousseau and Schelp in 1978. Since then, Size-Ramsey numbers have been studied with particular focus on the case of trees and bounded degree graphs.Addressing a question posed by Erdős‚ Beck [2] proved that the size-Ramsey number of the path
is linear in by means of a probabilistic construction. In fact, Beck’s proof implies that and this upper bound was improved several times. Currently‚ the best known upper bound is due to Dudek and Prałat [4] which proved that . On the other hand‚ the first nontrivial lower bound for was provided by Beck and his result was subsequently improved by Dudek and Prałat [3] who showed that. The strongest known lower bound was proved recently by Bal and DeBiasio [1]../files/site1/files/%D8%AC%D9%88%D8%A7%D8%AF%DB%8C_%D9%85%DB%8C%D8%B1%D8%B9%D9%84%D8%A7%DB%8C%DB%8C.pdf
Type of Study: S |
Subject:
alg
Received: 2019/02/20 | Revised: 2022/05/7 | Accepted: 2019/11/4 | Published: 2021/12/1 | ePublished: 2021/12/1
Received: 2019/02/20 | Revised: 2022/05/7 | Accepted: 2019/11/4 | Published: 2021/12/1 | ePublished: 2021/12/1
| Rights and permissions | |
 |
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. |