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 ${\displaystyle r(G)}$, the Ramsey number of G, such that any complete graph on at least ${\displaystyle r(G)}$ 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 c_p so that any p-degenerate graph G on n vertices has Ramsey number at most c_p 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 c_p n vertices.

Before the full conjecture was proved, it was first settled in some special cases. It was proven for bounded-degree graphs by Chvátal et al. (1983); their proof led to a very high value of c_p, and improvements to this constant were made by Eaton (1998) and Graham, Rödl & Rucínski (2000). 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.[2] It is also known for subdivided graphs, graphs in which no two adjacent vertices have degree greater than two.[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 c_p such that, for any p-degenerate n-vertex graph G,

${\displaystyle r(G)\leq 2^{c_{p}{\sqrt {\log n}}}n.}$