Degree sequence packing 11/01/2017

Speaker: James Shook, NIST

Abstract: Two $n$ -vertex graphs $G_1$ and $G_2$ pack if it is possible to express $G_1$ and $G_2$ as edge-disjoint subgraphs of $K_n$ , or alternatively, if $G_1\subseteq \overline{G_2}$ . Let $G_1$ and $G_2$ be $n$ -vertex graphs with maximum degrees $\Delta(G_i)=\Delta_i$ for $i=1,2$ . A classic conjecture of Bollobas and Eldridge and, independently, Catlin says that if
$(1) \qquad (\Delta_1+1)(\Delta_2+1) \le n+1,$
then $G_1$ and $G_2$ pack. A sequence $\pi=(d_1,\ldots,d_n)$ is graphic if there is a simple graph $G$ with vertex set $\{v_1,\ldots,v_n\}$ such that the degree of $v_i$ is $d_i$ . $G$ is said to be a realization of $\pi$ . In this talk we show that graphic sequence analogs of the classic conjecture hold. In particular, if Equation (1) holds, then there exists some graph $G_{3}$ with the same vertex degrees as $G_{2}$ that packs with $G_{1}$ .