Extremal problems on packing of sparse graphs

A. Kostochka

University of Illinois

Abstract

A number of basic problems in graph theory can be stated as packing problems. Graphs (on n vertices each) pack, if there exists an edge disjoint placement of all these graphs into the complete graph .

Directions of studying packing of graphs were defined about 25 years ago by fundamental papers of Bollobás and Eldridge and Sauer and Spencer. In this talk, we discuss three conjectures of Bollobás and Eldridge. We prove a partial case of the main Bollobás-Eldridge-Catlin Conjecture. Apart from this, we extend a conjecture and disprove another conjecture from their paper. We apply obtained results on packing of two graphs to packing many sparse graphs.

March 17, 2005

At 3:30 in Wallace 430