On a graph packing conjecture by Bollobás, Eldridge and Catlin

详细信息    查看全文

• 作者：Hemanshu Kaul ; Alexandr Kostochka and Gexin Yu
• 关键词：Mathematics Subject Classification (2000) 05C35 ; 05C70
• 刊名：Combinatorica
• 出版年：2008
• 出版时间：July, 2008
• 年：2008
• 卷：28
• 期：4
• 页码：469-485
• 全文大小：457.0 KB
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Mathematics
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1439-6912

文摘

Two graphs G ₁ and G ₂ 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 (Δ(G ₁) + 1)(Δ(G ₂) + 1) ≤ n + 1, then G ₁ and G ₂ pack. Towards this conjecture, we show that for Δ(G ₁),Δ(G ₂) ≥ 300, if (Δ(G ₁) + 1)(Δ(G ₂) + 1) ≤ 0.6n + 1, then G ₁ and G ₂ pack. This is also an improvement, for large maximum degrees, over the classical result by Sauer and Spencer that G ₁ and G ₂ pack if Δ(G ₁)Δ(G ₂) < 0.5n.