Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647001 | Discrete Mathematics | 2016 | 8 Pages |
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.