Name
Abstract | ||
|---|---|---|
We study packings of graphs with given maximal degree. We shall prove that the (hitherto unproved) Bollobas-Eldridge-Catlin Conjecture holds in a considerably stronger form if one of the graphs is d-degenerate for d not too large: if d,@D"1,@D"2=1 and nmax{40@D"1ln@D"2,40d@D"2} then a d-degenerate graph of maximal degree @D"1 and a graph of order n and maximal degree @D"2 pack. We use this result to show that, for d fixed and n large enough, one can pack n1500d^2 arbitrary d-degenerate n-vertex graphs of maximal degree at most n1000dlnn. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.jctb.2007.05.002 | J. Comb. Theory, Ser. B |
Keywords | Field | DocType |
order n,graph packing,d-degenerate graph,d -degenerate graphs,n large enough,maximal degree,stronger form,maximum degree,arbitrary d-degenerate n-vertex graph,bollobas-eldridge-catlin conjecture | Discrete mathematics,Indifference graph,Combinatorics,Chordal graph,Degree (graph theory),Pathwidth,1-planar graph,Pancyclic graph,Mathematics,Maximal independent set,Split graph | Journal |
Volume | Issue | ISSN |
98 | 1 | Journal of Combinatorial Theory, Series B |
Citations | PageRank | References |
11 | 0.90 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Béla Bollobás | 1 | 2696 | 474.16 |
| Alexandr Kostochka | 2 | 97 | 13.04 |
| Kittikorn Nakprasit | 3 | 74 | 12.32 |