Article ID Journal Published Year Pages File Type
4647001 Discrete Mathematics 2016 8 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , ,