Immersions of graphs and digraphs

author: Bojan Mohar, Faculty of Mathematics and Physics, University of Ljubljana
published: May 4, 2015,   recorded: March 2015,   views: 2201


Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


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.

See Also:

Download slides icon Download slides: eurocg2015_mohar_graphs_01.pdf (4.9 MB)

Help icon Streaming Video Help

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: