SUBDIVIDED GRAPHS HAVE LINEAR RAMSEY NUMBERS

It is shown that the Ramsey number of any graph with n vertices in whi ch no two vertices of degree at least 3 are adjacent is at most 12n. I n particular, the above estimate holds for the Ramsey number of any n- vertex subdivision of an arbitrary graph, provided each edge of the or iginal graph is subdivided at least once. This settles a problem of Bu rr and Erdos. (C) 1994 John Wiley & Sons, Inc.