99-58: Proof of a Conjecture of Bollobás and Eldridge for Graphs with Maximum Degree 3

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