In mathematics, the Erdős–Burr conjecture is a problem concerning the Ramsey number of sparse graphs. The conjecture is named after Paul Erdős and Stefan Burr, and is one of many conjectures named after Erdős; it states that the Ramsey number of graphs in any sparse family of graphs should grow linearly in the number of vertices of the graph.
Contents
In 2015, a proof of the conjecture was announced by Choongbum Lee.
Definitions
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
The conjecture
In 1973, Paul Erdős and Stefan Burr 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.
Known results
Although a proof of full conjecture has not been published, it has been 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 cp, and improvements to this constant were made by Eaton (1998) and Graham, Rödl & Ruciński (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 Kp. 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, Fox & Sudakov (2009) showed that there exists a constant cp such that, for any p-degenerate n-vertex graph G,