کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4656674 | 1632973 | 2016 | 19 صفحه PDF | دانلود رایگان |
A graph G is r-Ramsey for a graph H , denoted by G→(H)rG→(H)r, if every r-colouring of the edges of G contains a monochromatic copy of H. The graph G is called r-Ramsey-minimal for H if it is r-Ramsey for H but no proper subgraph of G possesses this property. Let sr(H)sr(H) denote the smallest minimum degree of G over all graphs G that are r-Ramsey-minimal for H . The study of the parameter s2s2 was initiated by Burr, Erdős, and Lovász in 1976 when they showed that for the clique s2(Kk)=(k−1)2s2(Kk)=(k−1)2. In this paper, we study the dependency of sr(Kk)sr(Kk) on r and show that, under the condition that k is constant, sr(Kk)=r2⋅polylogr. We also give an upper bound on sr(Kk)sr(Kk) which is polynomial in both r and k , and we show that cr2lnr⩽sr(K3)⩽Cr2ln2rcr2lnr⩽sr(K3)⩽Cr2ln2r for some constants c,C>0c,C>0.
Journal: Journal of Combinatorial Theory, Series B - Volume 120, September 2016, Pages 64–82