We consider the following generalization of graph packing. Let $G_{ 1} = (V_{ 1}, E_{ 1})$ and $G_{ 2} = (V_{ 2}, E_{ 2})$ be graphs of order $n$ and $G_{ 3} = (V_{ 1} \cup V_{ 2}, E_{ 3})$ a bipartite graph. A bijection $f$ from $V_{ 1}$ onto $V_{ 2}$ is a list packing of the triple $(G_{ 1}, G_{ 2}, G_{ 3})$ if $uv \in E_{ 2}$ implies $f(u)f(v) \notin E_{ 2}$ and $vf(v) \notin E_{ 3}$ for all $v \in V_{ 1}$. We extend the classical results of Sauer and Spencer and Bollob\'{ a}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\'{ a}s--Eldridge Theorem, proving that if $\Delta (G_{ 1}) \leq n-2, \Delta(G_{ 2}) \leq n-2, \Delta(G_{ 3}) \leq n-1$, and $|E_1| + |E_2| + |E_3| \leq 2n-3$, then either $(G_{ 1}, G_{ 2}, G_{ 3})$ packs or is one of 7 possible exceptions. Hopefully, the concept of list packing will help to solve some problems on ordinary graph packing, as the concept of list coloring did for ordinary coloring.
Categories: math.CO