Abstract

A number of basic problems in graph theory can be stated as packing problems. Graphs G_1, G_2,...,G_k (on n vertices each) pack, if there exists an edge disjoint placement of all these graphs into the complete graph K_n. A famous example of a packing problem is the Hamilton cycle problem: the problem of existence of a spanning (Hamiltonian) cycle in an n-vertex graph G is equivalent to the question whether the n-cycle C_n packs with the complement of G. Another example: a graph G on n vertices is equitably k-colorable if and only if G packs with the n-vertex graph whose components are cliques with floor(n/k) or ceil(n/k) vertices.
Important examples of packing problems are problems on existence of a given subgraph, Turan-type problems and Ramsey-type problems. These examples (and many more) show that graph packing is a rather general problem. The talk will pay the main attention to packing sparse subgraphs. The sparseness will be measured mostly by the maximum degree of vertices or the largest average degree over the subgraphs.
The goal of the talk is to survey recent progress in studying extremal packing problems for graphs, with emphasis on sparse graphs.