On ramsey minimal graphs

A graph G is r-Ramsey-minimal with respect to a graph H if every r-coloring of the edges of G yields a monochromatic copy of H, but the same is not true for any proper subgraph of G. In this paper we show that for any integer k ≥ 3 and r ≥ 2, there exists a constant c > 1 such that for large enough n, there exist at least c ⁿ² nonisomorphic graphs on at most n vertices, each of which is r-Ramsey-minimal with respect to the complete graph K _k. Furthermore, in the case r = 2, we give an asymmetric version of the above result.