On graphs with small Ramsey numbers

Let R(G) denote the minimum integer N such that for every bicoloring of the edges of K-N, at least one of the monochromatic subgraphs contains G as a subgraph. We show that for every positive integer d and each gamma ,0 < <ga mma> < 1, there exists k = k(d, <gamma>) such that for every bipartite grap h G =(W, U; E) with the maximum degree of vertices in W at most d and \U \ less than or equal to \W \ (gamma), R(G) less than or equal to k \W \. This answers a question of Trotter. We give also a weaker bound on the Ramsey n umbers of graphs whose set of vertices of degree at least d + 1 is independ ent. (C) 2001 John Wiley & Sons, Inc.