Generalized Ramsey theory for graphs IV, the Ramsey multiplicity of a graph

Abstract

Abstract A Proper graph G has no isolated points. Its Ramsey number r(G) is the minimum p such that every 2‐coloring of the edges of K p contains a monochromatic G. The Ramsey multiplicity R(G) is the minimum number of monochromatic G in any 2‐coloring of K r(G) . With just one exception, namely K 4 , we determine R(G) for proper graphs with at most 4 points. For the stars K 1,n , it is shown that R = 2n when n is odd and R = 1 when n is even. We conclude with the conjecture that for a proper graph, R(G) = 1 if and only if G = K 2 or K 1,n with n even.