On the minimum degree of minimal Ramsey graphs for multiple colours

A graph G is r-Ramsey for a graph H, denoted by G -> (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 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(2) was initiated by Burr, Erdos, and Lovasz in 1976 when they showed that for the clique s(2)(K-k) = (k - 1)(2). In this paper, we study the dependency of s(r)(K-k) on 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-k) which is polynomial in both r and k, and we show that cr(2) ln r <= s(r)(K-3) <= Cr-2 In-2 r for some constants c, C > 0. (C) 2016 Elsevier Inc. All rights reserved.