Two simple $n$-vertex graphs $G_{ 1}$ and $G_{ 2}$, with respective maximum degrees $\Delta_{ 1}$ and $\Delta_{ 2}$, are said to pack if $G_{ 1}$ is isomorphic to a subgraph of the complement of $G_{ 2}$. The BEC conjecture by Bollob\'{ a}s, Eldridge, and Catlin, states that if $(\Delta_{ 1}+1)(\Delta_{ 2}+1)\leq n+1$, then $G_{ 1}$ and $G_{ 2}$ pack. The BEC conjecture is true when $\Delta_{ 1}=2$ and has been confirmed for a few other classes of graphs with various conditions on $\Delta_{ 1}$, $\Delta_{ 2}$, or $n$. We show that if \[(\Delta_{ 1}+1)(\Delta_{ 2}+1)\leq n+\min\{ \Delta_{ 1},\Delta_{ 2}\},\] then there exists a simple graph with an identical degree sequence as $G_{ 1}$ that packs with $G_{ 2}$. However, except for a few cases, we show that this bound is not sharp. As a consequence of our work, we confirm the BEC conjecture if $G_{ 1}$ is the vertex disjoint union of a unigraph and a forest $F$ such that either $F$ has at least $\Delta_{ 2}+1$ components or at most $2\Delta_{ 2}-1$ edges.
Categories: math.CO