























Two simple $n$-vertex graphs $G_{1}$ and $G_{2}$, with respective maximum degrees $Δ_{1}$ and $Δ_{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 $(Δ_{1}+1)(Δ_{2}+1)\leq n+1$, then $G_{1}$ and $G_{2}$ pack. The BEC conjecture is true when $Δ_{1}=2$ and has been confirmed for a few other classes of graphs with various conditions on $Δ_{1}$, $Δ_{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 $Δ_{2}+1$ components or at most $2Δ_{2}-1$ edges.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。