Ramsey for complete graphs with a dropped edge or a triangle

Abstract Let K [ k , t ] be the complete graph on k vertices from which a set of edges, induced by a clique of order t , has been dropped (note that K [ k , 1 ] is just K k ). In this paper we study R ( K [ k 1 , t 1 ] , … , K [ k r , t r ] ) (the smallest integer n such that for any r -edge coloring of K n there always occurs a monochromatic K [ k i , t i ] for some i ). We first present a general upper bound (containing the well-known Graham-Rodl upper bound for complete graphs in the particular case when t i = 1 for all i ). We then focus our attention to when r = 2 , and to dropped cliques of order 2 and 3 (edges and triangles). We give the exact value for R ( K [ n , 2 ] , K [ 4 , 3 ] ) and R ( K [ n , 3 ] , K [ 4 , 3 ] ) for all n ≥ 2 .