In mathematics, the Burr–Erdős conjecture was a problem concerning the Ramsey number of sparse graphs.
[1] If G is an undirected graph, then the degeneracy of G is the minimum number p such that every subgraph of G contains a vertex of degree p or smaller.
It was proven for bounded-degree graphs by Chvátal et al. (1983); their proof led to a very high value of cp, and improvements to this constant were made by Eaton (1998) and Graham, Rödl & Rucínski (2000).
[3] For arbitrary graphs, the Ramsey number is known to be bounded by a function that grows only slightly superlinearly.
Specifically, Fox & Sudakov (2009) showed that there exists a constant cp such that, for any p-degenerate n-vertex graph G,