Proof of a Packing Conjecture of Bollobás
Proof of a Packing Conjecture of Bollobás
复制标题
Bollobás 装箱猜想的证明
DOI：
10.1017/s0963548300001620
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
E. Szemerédi
中科院分区：
文献类型：
--
作者：
J. Komlos;G. N. Sárközy;E. Szemerédi
Béla Bollobás [1]发表了以下评论。对于任何正整数Δ和真实的0 < c < ½，存在具有以下性质的n0。若n ≥ n0，T是一个n阶最大度为Δ的树，G是一个n阶最大度不超过cn的图，则T和G有一个packing.我们在这里证明这个猜想。辅助定理2.1是独立的兴趣。
Béla Bollobás [1] conjectured the following. For any positive integer Δ and real 0 < c < ½ there exists an n0 with the following properties. If n ≥ n0, T is a tree of order n and maximum degree Δ, and G is a graph of order n and maximum degree not exceeding cn, then there is a packing of T and G. Here we prove this conjecture. Auxiliary Theorem 2.1 is of independent interest.