Let G 1 and G 2 be simple 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ás and Eldridge [5] asserts that if (Δ(G 1)+1) (Δ(G 2)+1) ≤ n + 1 then there is a packing of G 1 and G 2. We prove this conjecture when Δ(G 1) = 3, for sufficiently large n.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Author information
Authors and Affiliations
Corresponding author
Additional information
* This work was supported in part by a grant from National Science Foundation (DMS-9801396).
† Partially supported by OTKA T034475.
‡ Part of this work was done while the authors were graduate students at Rutgers University; Research partially supported by a DIMACS fellowship.
Rights and permissions
About this article
Cite this article
Csaba†‡, B., Shokoufandeh‡, A. & Szemerédi, E. Proof of a Conjecture of Bollobás and Eldridge for Graphs of Maximum Degree Three*. Combinatorica 23, 35–72 (2003). https://doi.org/10.1007/s00493-003-0013-4
Received:
Issue Date:
DOI: https://doi.org/10.1007/s00493-003-0013-4