Working Seminar on Formal Models, Discrete Structures, and Algorithms

Strong immersions in 4-edge connected graphs

Tereza Klimošová (Warwick)

When: October 20, 2:00pm

Where: room C417


A graph H is strongly immersed in G if G is obtained from H by a sequence of vertex splittings (i.e., lifting some pairs of incident edges and removing the vertex) and edge removals. Equivalently, vertices of H are mapped to distinct vertices of G (branch vertices) and edges of H are mapped to pairwise edge-disjoint paths in G, each of them joining the branch vertices corresponding to the ends of the edge and not containing any other branch vertices.

The Grid-Minor Theorem says that for fixed g, every graph of large enough tree-width contains a g x g grid as a minor. We have proven that every four-edge-connected graph of large enough tree-width contains a g x g grid as an immersion (and hence contains any fixed graph with maximum degree at most four as an immersion). Moreover, we have shown that there exists a function d:N→N such that for all graphs H and G, if G contains a strong immersion of the star K_{1,d(Delta(H))|V(H)|} whose branch vertices are Delta(H)-edge-connected to one another, then H is strongly immersed in G. This has a number of structural consequences for graphs avoiding a strong immersion of H. In particular, a class C of simple 4-edge-connected graphs contains all graphs of maximum degree 4 as strong immersions if and only if C has either unbounded maximum degree or unbounded tree-width.

The talk is based on joint work with Maria Chudnovsky, Zdeněk Dvořák and Paul Seymour.