  The Ramsey number r(H) of a graph H is the minimum positive integer N such
that every two-coloring of the edges of the complete graph K_N on N vertices
contains a monochromatic copy of H. A graph H is d-degenerate if every subgraph
of H has minimum degree at most d. Burr and Erd\H{o}s in 1975 conjectured that
for each positive integer d there is a constant c_d such that r(H) \leq c_dn
for every d-degenerate graph H on n vertices. We show that for such graphs r(H)
\leq 2^{c_d\sqrt{\log n}}n, improving on an earlier bound of Kostochka and
Sudakov. We also study Ramsey numbers of random graphs, showing that for d
fixed, almost surely the random graph G(n,d/n) has Ramsey number linear in n.
For random bipartite graphs, our proof gives nearly tight bounds.
