Original Burr–Erdős conjecture for pairs of bounded-arboricity graphs

For graphs H1H_1 and H2H_2, let r(H1,H2)r(H_1,H_2) be the least integer nn such that every red-blue edge-coloring of KnK_n contains a red copy of H1H_1 or a blue copy of H2H_2. The arboricity of a graph is the minimum number of forests into which its edge set can be partitioned. Original Burr–Erdős conjecture. For every natural number dd, there exists a constant cc such that, for every pair of graphs H1H_1 and H2H_2 each having arboricity at most dd,

r(H1,H2)c(V(H1)+V(H2)).r(H_1,H_2)\leq c\bigl(|V(H_1)|+|V(H_2)|\bigr).

This is the original pair-version formulation underlying the degenerate-graph perspective. The source presents it as the original conjecture and does not give a resolution here.

Sources & referencesView supporting material

Primary source

Choongbum Lee, “Ramsey numbers of degenerate graphs”, arXiv:1505.04773 (2016).

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.