Proof of the Bollobas-Catlin-Eldridge conjecture

Proof of the Bollobas-Catlin-Eldridge conjecture

-
Gabor Kun, IAS
Fine Hall 224

We say that two graphs $G$ and $H$ pack if $G$ and $H$ can be embedded into the same vertex set such that the images of the edge sets do not overlap. Bollobas and Eldridge, and independently Catlin conjectured that if the graphs $G$ and $H$ on $n$ vertices with maximum degree $M(G)$ and $M(H)$, respectively, satisfy $(M(G) + 1)(M(H) + 1) ≤ n + 1$ then $G$ and $H$ pack. Aigner and Brandt and, independently, Alon and Fischer proved this in the case $M(G),M(H) < 3$, Csaba, Shokoufandeh and Szemeredi proved the conjecture if $M(G),M(H) < 4$. Bollobas, Kostochka and Nakprasit settled the case when one of the graphs is degenerate. Kaul, Kostochka and Yu showed that if $M(G)M(H) < 3/5n$ and the maximal degrees are large enough then $G$ and $H$ pack. We prove the conjecture for graphs with at least $10^8$ vertices.