## DIMACS TR: 99-58

## 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

DIMACS Home Page