## Proof of a Conjecture of Bollobás and Eldridge for Graphs with Maximum Degree 3

### Authors: Béla Csaba, Ali Shokoufandeh, Endre Szemerédi

ABSTRACT

Let \$G_1\$ and \$G_2\$ be graphs on \$n\$ vertices. If there are edge-disjoint copies of \$G_1\$ and \$G_2\$ in \$K_n\$, then we say there is a packing of \$G_1\$ and \$G_2\$. A conjecture of Bollob\'as and Eldridge ~\cite{be78} asserts that, if \$(\Delta(G_1)+1)(\Delta(G_2)+1)\le n+1\$ then there is a packing of \$G_1\$ and \$G_2\$. We prove this conjecture when \$\Delta(G_1)=3\$, for sufficiently large \$n\$.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1999/99-58.ps.gz