On graphs with small Ramsey numbers. II. (Q558242)

[For Part I see \textit{A. V. Kostochka} and \textit{V. Rödl}, J. Graph. Theory 37, 198--204 (2001; Zbl 0994.05094).] A graph \(G\) is \(d\)-degenerate if every subgraph of \(G\) has a vertex of degree at most \(d\). Burr and Erdős conjectured that the Ramsey number of a \(d\)-degenerate graph is linear, i.e., \(R(G,G)\leq c | V(G)| \), for some appropriate constant \(c=c(d)\). The authors prove the following statement in this spirit. If \(G_1\) and \(G_2\) are \(d\)-degenerate, then \(R(G_1,G_2)\leq cn\Delta (G_1)\), where \(c=c(d)\) and \(\Delta\) is the maximum degree of \(G_1\). An immediate corollary is that the Ramsey number of a \(d\)-degenerate graph is quadratic at most.