Burr–Erdős conjecture
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. A graph with degeneracy "p" is called "p"-degenerate. Equivalently, a "p"-degenerate graph is a graph that can be reduced to the empty graph by repeatedly removing a vertex of degree "p" or smaller. It follows from Ramsey's theorem that for any graph "G" there exists a least integer 
formula_1, the "Ramsey number" of "G", such that any complete graph on at least formula_1 vertices whose edges are coloured red or blue contains a monochromatic copy of "G". For instance, the Ramsey number of a triangle is 6: no matter how the edges of a complete graph on six vertices are colored red or blue, there is always either a red triangle or a blue triangle. In 1973, Stefan Burr and Paul Erdős made the following conjecture:
For every integer "p" there exists a constant "cp" so that any "p"-degenerate graph "G" on "n" vertices has Ramsey number at most "cp n". That is, if an "n"-vertex graph "G" is "p"-degenerate, then a monochromatic copy of "G" should exist in every two-edge-colored complete graph on "cp n" vertices. Before the full conjecture was proved, it was first settled in some special cases. It was proven for bounded-degree graphs by ; their proof led to a very high value of "c""p", and improvements to this constant were made by and . More generally, the conjecture is known to be true for "p"-arrangeable graphs, which includes graphs with bounded maximum degree, planar graphs and graphs that do not contain a subdivision of "K""p". It is also known for subdivided graphs, graphs in which no two adjacent vertices have degree greater than two. For arbitrary graphs, the Ramsey number is known to be bounded by a function that grows only slightly superlinearly. Specifically, showed that there exists a constant "cp" such that, for any "p"-degenerate "n"-vertex graph "G",
formula_3
The conjecture
In mathematics, the Burr–Erdős conjecture was a problem concerning the Ramsey number of sparse graphs.