Volume 7, Issue 3 (Vol.7, No.3, 2021)                   mmr 2021, 7(3): 485-494 | Back to browse issues page

XML Persian Abstract Print

1- Isfahan University of Technology , rjavadi@cc.iut.ac.ir
2- Isfahan University of Technology
Abstract:   (844 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].
Full-Text [PDF 655 kb]   (219 Downloads)    
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

Rights and permissions
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.