Burr–Erdős conjecture

About 53 years old · traced to 1973

For an undirected graph $G$ , the degeneracy of $G$ is the minimum integer $p$ such that every subgraph of $G$ contains a vertex of degree at most $p$ ; a graph of degeneracy at most $p$ is called $p$ -degenerate. For a graph $G$ , let $r(G)$ denote the least integer $N$ such that in every colouring of the edges of the complete graph $K_N$ with two colours (red and blue) there is a monochromatic subgraph isomorphic to $G$ .

For every integer $p \ge 0$ there exists a constant $c_p$ such that every $p$ -degenerate graph $G$ on $n$ vertices satisfies

r(G) \le c_p n.

References

Primary source

Wikipedia

Additional references

Wikipedia, Burr–Erdős conjecture, the article this problem comes from.

unsolved-problem

Posted 2 months ago

Progress summary

Refreshed 1 month ago

Claimed solved

The conjecture is now a theorem: every graph with a fixed sparsity bound must appear in one colour of every sufficiently large two-coloured complete graph, using only a constant multiple of its own size.

The Burr–Erdős conjecture asserts that, for each fixed degeneracy bound $p$ , the relevant two-colour Ramsey number is at most a constant multiple of the graph’s number of vertices. Burr and Erdős posed it in the 1970s; sources give 1973 or 1975.

Known results

Bounded-maximum-degree graphs: Chvátal, Rödl, Szemerédi, and Trotter, 1983.
Further quantitative improvements: Eaton, 1998; Graham, Rödl, and Ruciński, 2000.
$p$ -arrangeable classes, including planar graphs, were settled before the full conjecture.
Fox and Sudakov, 2009: $r(G)\leq 2^{c_p\sqrt{\log n}}n$ for $p$ -degenerate $n$ -vertex graphs.

2017 proof by Choongbum Lee

Lee proved the full conjecture, with the paper published in the Annals of Mathematics in 2017. Later papers independently describe the conjecture as resolved; no retrieved source reports a counterexample, gap, withdrawal, or competing unresolved objection.

Current status (as of August 2026): The Burr–Erdős conjecture is settled by Lee’s 2017 theorem; no substantive part of the stated conjecture remains open.

Sources

No solutions have been posted yet.