Packing minor-closed families of graphs into complete graphs

详细信息    查看全文

• 作者：Silvia Messuti^a ; ^{silvia.messuti@math.uni-hamburg.de" class="auth_mail" title="E-mail the corresponding author} ; Vojtěch Rö ; dl^b ; ^{rodl@mathcs.emory.edu" class="auth_mail" title="E-mail the corresponding author} ; Mathias Schacht^a ; ^{schacht@math.uni-hamburg.de" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Packings ; Minor-closed families ; Trees
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2016
• 出版时间：July 2016
• 年：2016
• 卷：119
• 期：Complete
• 页码：245-265
• 全文大小：456 K

文摘

Motivated by a conjecture of Gyárfás, recently Böttcher, Hladký, Piguet, and Taraz showed that every collection class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895616000289&_mathId=si1.gif&_user=111111111&_pii=S0095895616000289&_rdoc=1&_issn=00958956&md5=a6afed6468d7a3f426bda4e244ca1000" title="Click to view the MathML source">T₁,…,T_tclass="mathContainer hidden">class="mathCode">$T_1,\dots ,T_t$ of trees on n   vertices with class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895616000289&_mathId=si2.gif&_user=111111111&_pii=S0095895616000289&_rdoc=1&_issn=00958956&md5=821178c0be3c7a846e3e09408dce9e2d">class="imgLazyJSB inlineImage" height="21" width="120" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0095895616000289-si2.gif">class="mathContainer hidden">class="mathCode">${\sum }_{i=1}^{t}e(T_i)⩽\left(\begin{array}{c}\hfill n\hfill \\ \hfill 2\hfill \end{array}\right)$ and with bounded maximum degree can be packed into the complete graph on class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895616000289&_mathId=si3.gif&_user=111111111&_pii=S0095895616000289&_rdoc=1&_issn=00958956&md5=acf7658e2d7f28b86937bba89a5ae8d7" title="Click to view the MathML source">(1+o(1))nclass="mathContainer hidden">class="mathCode">$(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.