Burr–Erdős conjecture for degenerate graphs

Let dNd\in\mathbb{N}. A graph is dd-degenerate when its vertices admit an ordering in which every vertex has at most dd neighbors earlier in the ordering. Burr–Erdős conjecture. There exists c=c(d)>0c=c(d)>0 such that every 22-edge-colored KnK_n contains a copy of every dd-degenerate graph on at most cncn vertices. The source states that this conjecture was recently confirmed by Lee, so the result is solved.

Sources & referencesView supporting material

Primary source

Jan Corsten, Louis DeBiasio and Paul McKenney, “Density of monochromatic infinite subgraphs II”, arXiv:2007.14277 (2025).

Additional references

3 papers in this index state this conjecture (2007–2020). The statement above is taken from the most recent of them; the others are arXiv:0901.3541, arXiv:math/0703653.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.