Bollobás--Eldridge--Catlin conjecture for bounded-degree spanning subgraphs

About 1 year old · traced to

Let Δ\Delta be a positive integer. Let GG and HH be nn-vertex graphs, and write δ(G)\delta(G) for the minimum degree of GG and Δ(H)\Delta(H) for the maximum degree of HH.

Bollobás--Eldridge--Catlin conjecture. If

δ(G)≥ΔΔ+1n\delta(G)\geq \frac{\Delta}{\Delta+1}n

and Δ(H)≤Δ\Delta(H)\leq \Delta, then HH is a spanning subgraph of GG.

The conjecture remains open; the source notes that a proof for sufficiently large nn was announced by Kun in 2009, but no manuscript had appeared.

References

Primary source

Peter Allen, Julia Böttcher, Yoshiharu Kohayakawa and Mihir Neve, “Robustness of the Sauer-Spencer Theorem”, arXiv:2507.03676 (2025).

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.