Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, September 24, 2015, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Frank Mousset
A sequence G1,...,Gt of graphs is said to pack into a graph G if G contains G1,...,Gt as edge-disjoint subgraphs. I will talk about the following result. Let F be a non-trivial minor-closed family of graphs (for example, the family of planar graphs). Then for all positive constants x and D and for every sufficiently large integer n, every sequence G1,...,Gt of graphs in F such that
- v(Gi) ≤ n for all i,
- e(G1) + ... + e(Gt) ≤ (1-x) n(n-1)/2, and
- the maximum degree of each Gi is at most D,
packs into the complete graph on n vertices. This improves a very similar result of Messuti, Rödl, and Schacht in which the graphs are required to have at most (1-x)n vertices.
Joint work with Asaf Ferber and Choongbum Lee.
Automatic MiSe System Software Version 1.4803M | admin login