New Results in Graph Packing

Several basic problems in graph theory can be stated as packing problems. Let G₁ and G₂ be graphs of order at most n, with maximum degree Δ₁and Δ₂, respectively. We say that G₁ and G₂ pack if their vertex sets map injectively into {1,...,n} so that the images of the edge sets are disjoint. The concept of graph packing generalizes various extremal graph problems, including problems on fixed subgraphs (such as the Hamiltonian Cycle problem), forbidden subgraphs (Turan-type problems), and equitable coloring. The study of packings of graphs was started in the 1970s by Sauer and Spencer, and by Bollobas and Eldridge. Graph packing results have also been widely applied to studying the computational complexity of graph properties.

In 1978, Sauer and Spencer showed that if 2Δ₁Δ₂< n, then G₁ and G₂ pack. Sauer-Spencer theorem is sharp, and we (with A. Kostochka) extend it by characterizing the extremal graphs. This result can thought of as a small step towards the well-known Bollobas-Eldridge graph packing conjecture (1978): if (Δ₁+1)(Δ₂+1)<= n+1, then G₁ and G₂ pack. If true, this conjecture would be sharp and would be a considerable extension of the Hajnal-Szemeredi theorem on equitable colorings. The conjecture has only been proved when Δ₁<=2, or Δ₁=3, and n is huge. We (with A. Kostochka and G. Yu) prove the best current result towards this conjecture, further extending the Sauer-Spencer theorem.