Immersions of graphs and digraphs
published: May 4, 2015, recorded: March 2015, views: 2200
Report a problem or upload filesIf 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.
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.
Download slides: eurocg2015_mohar_graphs_01.pdf (4.9 MB)
Link this pageWould you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !
Write your own review or comment: