TY - JOUR

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

AU - Kaul, Hemanshu

AU - Kostochka, Alexandr

AU - Yu, Gexin

N1 - Funding Information:
* This work was supported in part by NSF grant DMS-0400498. The work of the second author was also partly supported by NSF grant DMS-0650784 and grant 05-01-00816 of the Russian Foundation for Basic Research. The work of the third author was supported in part by NSF grant DMS-0652306.

PY - 2008/7

Y1 - 2008/7

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

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

UR - http://www.scopus.com/inward/record.url?scp=58549104712&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=58549104712&partnerID=8YFLogxK

U2 - 10.1007/s00493-008-2278-0

DO - 10.1007/s00493-008-2278-0

M3 - Article

AN - SCOPUS:58549104712

SN - 0209-9683

VL - 28

SP - 469

EP - 485

JO - Combinatorica

JF - Combinatorica

IS - 4

ER -