Immersions of graphs and digraphs
May 4, 2015 2248 views 
A graph G contains another graph H as an immersion if there is an injective mapping ι : V (H) → V (G) and for each edge uv ∈ E(H) there is a path Puv in G joining vertices ι(u) and ι(v) such that the paths Puv (uv ∈ E(H)) are pairwise edge-disjoint. If the paths are internally disjoint from ι(V (H)), then we speak of a strong immersion. One can define (strong) immersions of digraphs in the same way. Nash-Williams conjectured that graphs are well-quasi ordered for the relation of immersion containment. The conjecture was proved by Robertson and Seymour (Graph minors XXIII. Nash-Williams’ immersion conjecture, J. Combinatorial Theory, Ser. B 100 (2010), 181–205) for weak immersions. Recent interest in graph and digraph immersions resulted in a variety of new discoveries. The speaker will enlighten some of these achievements.