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 γ,0 < γ < 1, there exists k  =  k ( d ,γ) such that for every bipartite graph G  = ( W , U ; E ) with the maximum degree of vertices in W at most d and $|U|\leq |W|^{\gamma }$ , $R(G)\leq k|W|$ . This answers a question of Trotter. We give also a weaker bound on the Ramsey numbers of graphs whose set of vertices of degree at least d  + 1 is independent. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 198–204, 2001