Erdős–Burr conjecture
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.
In 2015, a proof of the conjecture was announced by Choongbum Lee.
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 Ramsey number of G, such that any complete graph on at least 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.
...
Wikipedia