2026/07/20 by Peter Allen, Julia Böttcher, Jozef Skokan +1
#math.CO
The celebrated Bollobás-Eldridge-Catlin packing conjecture states that every n-vertex graph G with minimum degree at least (1-(1)/(Δ+1)) n contains every n-vertex graph H of maximum degree at most Δ. Despite considerable attention, the conjecture remains widely open. We show that for bipartite H this threshold can be greatly improved: there is an absolute constant c>0 such that every n-vertex graph G with minimum degree at least (1-c\fraclogΔΔ)n contains every n-vertex bipartite graph H of maximum degree at most Δ, provided Δ is not too large compared to n. Moreover, we prove that this logarithmic improvement is best possible up to the value of the constant.