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 -