Bojan Mohar: Average degree condition forcing complete graph immersion
Datum objave: 27. 10. 2010
Seminar za teorijo grafov in algoritme
Četrtek 28.10. ob 12:15h v predavalnici 3.05 na Jadranski 21
An immersion of a graph $H$ into a graph $G$ is a one-to-one mapping
$f: V(H) \to V(G)$ and a collection of edge-disjoint paths,
one for each edge of $H$, such that the path $P_{uv}$ corresponding
to edge $uv$ has endpoints $f(u)$ and $f(v)$.
We prove that every simple graph with average degree $\Omega(k)$
immerses the complete graph $K_k$. Moreover, if $G$ is dense enough,
then there is an immersion of $K_k$ in which each path $P_{uv}$ is of
length precisely 2. This is joint work with Matt DeVos, Zdenek Dvorak,
Jacob Fox, Jessica McDonald, and Diego Scheide.
