Packing d-degenerate graphs

DOI10.1016/J.JCTB.2007.05.002MaRDI QIDQ2464154zbMATH OpenOpenAlexFDO

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

Publication date 10 December 2007

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jctb.2007.05.002

zbMATH Keywords

\(d\)-degenerate graphgraph packingmaximum degree

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

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.

Recommendations

• On a graph packing conjecture by Bollobás, Eldridge and Catlin
• Packing degenerate graphs
• Packing graphs of bounded codegree
• A near packing of two graphs
• Perfectly packing graphs with bounded degeneracy and many leaves

Cites work

• 2-factors in dense graphs
• Edge disjoint placement of graphs
• Embedding Arbitrary Graphs of Maximum Degree Two
• Equitable and proportional coloring of trees
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 3517201 (Why is no real title available?)
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• On Equitable Coloring of d-Degenerate Graphs
• On Two Conjectures on Packing of Graphs
• Packings of graphs and applications to computational complexity
• Proof of a conjecture of Bollobás and Eldridge for graphs of maximum degree three

Cited in

(19)

• A decomposition of 2-weak vertex-packing polytopes
• Packing degenerate graphs greedily
• Packing two graphs of even girth 10
• Orthogonal decomposition and packing of complete graphs
• Packing a number of copies of a \(( p , q )\)-graph
• Packing degenerate graphs
• On a packing problem of Alon and Yuster
• Extremal theorems for degree sequence packing and the two-color discrete tomography problem
• Efficient graph packing via game colouring
• scientific article; zbMATH DE number 4103133 (Why is no real title available?)
• A blow-up lemma for approximate decompositions
• Embedding spanning bipartite graphs of small bandwidth
• Packing graphs of bounded codegree
• Perfectly packing graphs with bounded degeneracy and many leaves
• Graph and hypergraph packing
• Packing of the k-power of Hamilton cycles
• A generalization of the graph packing theorems of Sauer-Spencer and Brandt
• Packing of graphs with small product of sizes
• On a graph packing conjecture by Bollobás, Eldridge and Catlin

This page was built for publication: Packing \(d\)-degenerate graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2464154)