Combinatorics Seminar- Degree Sequence Packing

Speaker: James Shook, NIST
Date and time: Wednesday, November 1, 4-5pm
Place: Rome 771
Title:  Degree Sequence Packing
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 is a subgraph of the complement of G_2. Let G_1 and G_2 be n-vertex graphs with maximum degrees D_i for i=1,2. A classic conjecture of Bollobas and Eldridge  and, independently, Catlin says that if (D_1+1)(D_2+1)<n+2, then G_1 and G_2 pack. A sequence (d_1,...,d_n) is graphic if there is a simple graph G with vertex set {v_1,...,v_n} such that the degree of v_i is d_i.  We say that G is a realization of the sequence.  In this talk we show that graphic sequence analogs of the classic conjecture hold. In particular, if the inequality above holds, then there exists some graph G_3 with the same vertex degrees as G_2 that packs with G_1.