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$.
DIMACS Home Page