## Abstract

A graph G is r-Ramsey for a graph H, denoted by G→(

*H*)*, if every*_{r}*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*s*(_{r}*H*) denote the smallest minimum degree of*G*over all graphs*G*that are*r*-Ramsey-minimal for*H*. The study of the parameter*s*was initiated by Burr, Erdos, and Lovász in 1976 when they showed that for the clique_{2}*s*(_{2}*K*)=(_{k}*k*-1)^{2}. In this paper, we study the dependency of*s*(_{r}*K*) on_{k}*r*and show that, under the condition that k is constant,*s*(_{r}*K*)=_{k}*r*^{2}•polylog*r*. We also give an upper bound on*s*(_{r}*K*) which is polynomial in both_{k}*r*and*k*, and we show that*cr*ln^{2}*r*≤*s*(_{r}*K*) ≤_{3}*Cr*^{2}ln^{2}*r*for some constants*c*, C>0.Original language | English |
---|---|

Pages (from-to) | 64-82 |

Number of pages | 19 |

Journal | Journal of Combinatorial Theory, Series B |

Volume | 120 |

DOIs | |

Publication status | Published - 2016 |

## Keywords

- Erdos-Rogers function
- Graph theory
- Minimal Ramsey graphs
- Minimum degree
- Ramsey theory