{"id":"arxiv/2607.17808","url":"https://arxiv.org/abs/2607.17808","tags":["math.CO"],"score":0,"title":"Breaking the Bollobás-Eldridge-Catlin Barrier for Bipartite Graphs","domain":"math.CO","source":"arxiv","authors":["Peter Allen","Julia Böttcher","Jozef Skokan","Benny Sudakov"],"reviews":0,"subject":"math.CO","summary":"The celebrated Bollobás-Eldridge-Catlin packing conjecture states that every $n$-vertex graph $G$ with minimum degree at least $\\big(1-\\frac{1}{Δ+1}\\big) 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 $ \\big(1-c\\frac{\\logΔ}Δ\\big)n $ contains every $n$-vertex bipartite graph $H$ of maximum degree at most $Δ$, provided $Δ$ is not too…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-20","reactions":{}}