کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647001 | 1342321 | 2016 | 8 صفحه PDF | دانلود رایگان |
We consider the following generalization of graph packing. Let G1=(V1,E1)G1=(V1,E1) and G2=(V2,E2)G2=(V2,E2) be graphs of order nn and G3=(V1∪V2,E3)G3=(V1∪V2,E3) a bipartite graph. A bijection ff from V1V1 onto V2V2 is a list packing of the triple (G1,G2,G3)(G1,G2,G3) if uv∈E1uv∈E1 implies f(u)f(v)∉E2f(u)f(v)∉E2 and for all v∈V1v∈V1, vf(v)∉E3vf(v)∉E3. We extend the classical results of Sauer and Spencer and Bollobás and Eldridge on packing of graphs with small sizes or maximum degrees to the setting of list packing. In particular, we extend the well-known Bollobás–Eldridge Theorem, proving that if Δ(G1)≤n−2,Δ(G2)≤n−2,Δ(G3)≤n−1Δ(G1)≤n−2,Δ(G2)≤n−2,Δ(G3)≤n−1, and |E1|+|E2|+|E3|≤2n−3|E1|+|E2|+|E3|≤2n−3, then either (G1,G2,G3)(G1,G2,G3) packs or is one of 7 possible exceptions.
Journal: Discrete Mathematics - Volume 339, Issue 8, 6 August 2016, Pages 2178–2185