Embedding spanning graphs into dense and sparse graphs
|
Tue, 25/05/2010 14:30 |
Anusch Taraz (Munich) |
Combinatorial Theory Seminar  |
L3 |
In this talk we will first survey results which guarantee the existence of
spanning subgraphs in dense graphs. This will lead us to the proof of the
bandwidth-conjecture by Bollobas and Komlos, which states that any graph
with minimum degree at least  contains every r-chromatic graph
with bounded maximum degree and sublinear bandwidth as a spanning subgraph.
We will then move on to discuss the analogous question for a host graph that
is obtained by starting from a sparse random graph G(n,p) and deleting a
certain portion of the edges incident at every vertex.
This is joint work with J. Boettcher, Y. Kohayakawa and M. Schacht. |
|||