Verstraëte's conjecture on packing graph subdivisions

Given graphs FF and GG, a subdivision packing of FF in GG is a collection of pairwise vertex-disjoint copies of subdivisions of FF. For a real number η>0\eta > 0 and a graph FF, let d0=d0(F,η)d_0=d_0(F,\eta) be a threshold degree. Verstraëte's conjecture. For every graph FF and every η>0\eta>0, there exists d0=d0(F,η)d_0=d_0(F,\eta) such that, for every integer dd0d\ge d_0, every dd-regular graph GG of order nn contains a subdivision packing covering all but at most ηn\eta n vertices of GG. This conjecture concerns approximate spanning packings in dense regular graphs; the paper establishes stronger perfect-packing results when the degree is linear in the order of the graph.

Sources & referencesView supporting material

Primary source

Shoham Letzter, Abhishek Methuku and Benny Sudakov, “Packing subgraphs in regular graphs”, arXiv:2509.26180 (2026).

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.