Packing \(d\)-degenerate graphs (Q2464154): Difference between revisions

The Bollobás-Eldridge-Catlin conjecture asserts that two \(n\)-vertex graphs of maximum degree \(\Delta_1\) and \(\Delta_2\) pack if \((\Delta_1+1)(\Delta_2+1) \leq n+1\). Under the additional hypothesis that the first graph is \(d\)-degenerate (i.e. every subgraph has a vertex of degree at most \(d\)), this paper establishes that when \(n > \max \{ 40\Delta_1\ln \Delta_2, 40 d \Delta_2 \}\), the two graphs pack. This is stronger than the stated conjecture when \(d\) is small. The extension to packing many \(d\)-degenerate graphs is also examined.