Packing a Degree Sequence Realization With A Graph

Abstract

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ás, Eldridge, and Catlin, states that if $({\Delta }_1+1)({\Delta }_2+1)\le 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 \[(Δ_{1}+1)(Δ_{2}+1)\leq n+\min\{Δ_{1},Δ_{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.