Packing d-degenerate graphs

Béla Bollobás, Alexandr Kostochka, Kittikorn Nakprasit

Research output: Contribution to journalArticlepeer-review


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).

Original languageEnglish (US)
Pages (from-to)85-94
Number of pages10
JournalJournal of Combinatorial Theory. Series B
Issue number1
StatePublished - Jan 2008


  • Graph packing
  • Maximum degree
  • d-Degenerate graphs

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Packing d-degenerate graphs'. Together they form a unique fingerprint.

Cite this