Graph Packing and Degree Sequences

Two graphs G and H are said to pack if there exists a simple graph that contains edge-disjoint copies of G and H. Two families of graphs F and F' are said to pack if there exist graphs G in F sand G' in F' such that G and G' pack.

In this talk we will mostly focus on packing of families of graphs that consist of all possible realizations of fixed degree sequences. We have the additional requirement that, unlike the usual graph packing, the vertices can not be permuted to allow packing.

We will give an overview of some long-standing problems in graph packing. We will present Sauer-Spencer type degree conditions for packing degree sequences, and extensions of Kundu's classical k-factor theorem on packing of a graphic sequence with an almost k-regular degree sequence.

Event Topic

Networks and Optimization