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

XML Persian Abstract Print

Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:

Javadi R, Miralaei M. Multicolor Size-Ramsey Number of Paths. mmr 2021; 7 (3) :485-494
URL: http://mmr.khu.ac.ir/article-1-2916-en.html
1- Isfahan University of Technology , rjavadi@cc.iut.ac.ir
2- Isfahan University of Technology
Abstract:   (798 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]   (201 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

Add your comments about this article : Your username or Email:

Send email to the article author

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

© 2024 CC BY-NC 4.0 | Mathematical Researches

Designed & Developed by : Yektaweb