Ramsey Numbers of Sparse Graphs Versus Complete Graphs

A graph \( G \) is Ramsey size-linear if \( R(G,H)=O(e(H)) \) for every graph \( H \) without isolated vertices. Erdős, Faudree, Rousseau and Schelp asked whether every graph in which each \( j \)-vertex subgraph spans at most \( 2j-3 \) edges is Ramsey size-linear (Erdős Problem \#566); for such \( G \) this predicts \( R(G,K_n)=O(n^2) \). The open cases on at most eight vertices reduce to \( 49 \) minimal graphs. All have treewidth three, so \( R(G,K_n)=O(n^3) \) by a result of Bradač, Gishboliner and Sudakov; only two had a better bound. We improve the bound for \( 25 \) further graphs, down to \( O(n^{7/3}/\log^{4/3}n) \) for four of them. For the graph\( J \) obtained from \( K_4 \) by subdividing one edge twice and gluing a triangle to each end edge of the subdivision path, we prove \( R(J,K_n)=O(n^{5/2}/\log^2n) \), by showing that second neighbourhoods inside the links of a \( J \)-free graph are independent sets. More generally, if \( G \) is built from a wheel \( W_k \) by gluing triangles on robust edges, the robust links of a \( G \)-free graph contain no \( k \)-cycle, which bounds degrees by \( R(C_k,K_n) \). We tabulate the best known bounds against \( K_n \) and \( K_{n,n} \)for all \( 49 \) graphs.