TY - JOUR

T1 - Packing d-degenerate graphs

AU - Bollobás, Béla

AU - Kostochka, Alexandr

AU - Nakprasit, Kittikorn

N1 - Funding Information:
E-mail addresses: bollobas@msci.memphis.edu (B. Bollobás), kostochk@math.uiuc.edu (A. Kostochka), kitnak@hotmail.com (K. Nakprasit). 1 Research supported by NSF grants CCR-0225610 and DMS-0505550. 2 Research supported by the NSF grants DMS-0099608 and DMS-0400498.

PY - 2008/1

Y1 - 2008/1

N2 - We study packings of graphs with given maximal degree. We shall prove that the (hitherto unproved) Bollobás-Eldridge-Catlin Conjecture holds in a considerably stronger form if one of the graphs is d-degenerate for d not too large: if d, Δ1, Δ2 ≥ 1 and n > max {40 Δ1 ln Δ2, 40 d Δ2} then a d-degenerate graph of maximal degree Δ1 and a graph of order n and maximal degree Δ2 pack. We use this result to show that, for d fixed and n large enough, one can pack frac(n, 1500 d2) arbitrary d-degenerate n-vertex graphs of maximal degree at most frac(n, 1000 d ln n).

AB - We study packings of graphs with given maximal degree. We shall prove that the (hitherto unproved) Bollobás-Eldridge-Catlin Conjecture holds in a considerably stronger form if one of the graphs is d-degenerate for d not too large: if d, Δ1, Δ2 ≥ 1 and n > max {40 Δ1 ln Δ2, 40 d Δ2} then a d-degenerate graph of maximal degree Δ1 and a graph of order n and maximal degree Δ2 pack. We use this result to show that, for d fixed and n large enough, one can pack frac(n, 1500 d2) arbitrary d-degenerate n-vertex graphs of maximal degree at most frac(n, 1000 d ln n).

KW - Graph packing

KW - Maximum degree

KW - d-Degenerate graphs

UR - http://www.scopus.com/inward/record.url?scp=36048963352&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=36048963352&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2007.05.002

DO - 10.1016/j.jctb.2007.05.002

M3 - Article

AN - SCOPUS:36048963352

SN - 0095-8956

VL - 98

SP - 85

EP - 94

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 1

ER -