Packing minor-closed families of graphs into complete graphs

DOI10.1016/J.JCTB.2016.03.003MaRDI QIDQ273186zbMATH OpenOpenAlexFDO

Authors Silvia Messuti, M. Schacht, Vojtěch Rödl

Publication date 21 April 2016

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

Full work available at URL https://arxiv.org/abs/1602.06780

zbMATH Keywords

minor-closed familiespackings

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83)

Abstract: Motivated by a conjecture of Gy'arf'as, recently B"ottcher, Hladk'y, Piguet, and Taraz showed that every collection $T_1,dots,T_t$ of trees on $n$ vertices with $$ and with bounded maximum degree, can be packed into the complete graph on $(1+o(1))n$ vertices. We generalise this result where we relax the restriction of packing families of trees to families of graphs of any given non-trivial minor-closed class of graphs.

Recommendations

• Packing minor closed families of graphs
• On the tree packing conjecture
• scientific article; zbMATH DE number 22649
• scientific article; zbMATH DE number 1043871
• Packing almost stars into the complete graph

Cites work

• A Separator Theorem for Nonplanar Graphs
• An approximate version of the tree packing conjecture
• Asymptotic behavior of the chromatic index for hypergraphs
• Every H-decomposition of K_n has a nearly resolvable alternative
• scientific article; zbMATH DE number 3765842 (Why is no real title available?)
• scientific article; zbMATH DE number 3604921 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Near perfect coverings in graphs and hypergraphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(21)

• On packing minors into connected matroids
• Packing degenerate graphs greedily
• Embedding rainbow trees with applications to graph labelling and decomposition
• A proof of Ringel's conjecture
• Optimal packings of bounded degree trees
• Packing degenerate graphs
• Packing spanning graphs from separable families
• A Short proof of the blow-up lemma for approximate decompositions
• Packing minor closed families of graphs
• A blow-up lemma for approximate decompositions
• Packing trees of unbounded degrees in random graphs
• Decompositions of quasirandom hypergraphs into hypergraphs of bounded degree
• Tree decompositions of graphs without large bipartite holes
• Almost all trees are almost graceful
• Decomposing almost complete graphs by random trees
• Perfectly packing graphs with bounded degeneracy and many leaves
• Graph and hypergraph packing
• Seven largest trees pack
• Extremal density for sparse minors and subdivisions
• Packing large balanced trees into bipartite graphs
• Ringel's tree packing conjecture in quasirandom graphs

This page was built for publication: Packing minor-closed families of graphs into complete graphs

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