On a graph packing conjecture by Bollobás, Eldridge and Catlin
On a graph packing conjecture by Bollobás, Eldridge and Catlin
复制标题
关于 Bollobás、Eldridge 和 Catlin 的图包装猜想
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Gexin Yu
中科院分区：
文献类型：
--
作者：
Hemanshu Kaul;A. Kostochka;Gexin Yu
如果存在两个 n 阶图 G1 和 G2 的顶点集到 [n] 的单射映射，使得边集的图像不相交，则这两个图 G1 和 G2 会打包。 1978 年，Bollobás 和 Eldridge，以及 Catlin 独立推测，如果 (Δ(G1) + 1)(Δ(G2) + 1) ≤ n + 1，则 G1 和 G2 打包。针对这个猜想，我们证明，对于 Δ(G1),Δ(G2) ≥ 300，如果 (Δ(G1) + 1)(Δ(G2) + 1) ≤ 0.6n + 1，则 G1 和 G2 打包。对于较大的最大度，这也是相对于 Sauer 和 Spencer 的经典结果的改进，即如果 Δ(G1)Δ(G2) < 0.5n，则 G1 和 G2 打包。
Two graphs G1 and G2 of order n pack if there exist injective mappings of their vertex sets into [n], such that the images of the edge sets are disjoint. In 1978, Bollobás and Eldridge, and independently Catlin, conjectured that if (Δ(G1) + 1)(Δ(G2) + 1) ≤ n + 1, then G1 and G2 pack. Towards this conjecture, we show that for Δ(G1),Δ(G2) ≥ 300, if (Δ(G1) + 1)(Δ(G2) + 1) ≤ 0.6n + 1, then G1 and G2 pack. This is also an improvement, for large maximum degrees, over the classical result by Sauer and Spencer that G1 and G2 pack if Δ(G1)Δ(G2) < 0.5n.