Towards a structure theory for immersions

ACO Colloquium
Friday, August 21, 2015 - 15:05
1 hour (actually 50 minutes)
Skiles 006
University of Rome "La Sapienza"

Refreshments will be served in the atrium immediately following the talk. Please join us to welcome the new class of ACO students.

Graph immersion is an alternate model for graph containment similar to graph minors or topological minors. The presence of a large clique immersion in a graph G is closely related to the edge connectivity of G. This relationship gives rise to an easy theorem describing the structure of graphs excluding a fixed clique immersion which serves as the starting point for a broader structural theory of excluded immersions. We present the highlights of this theory with a look towards a conjecture of Nash-Williams on the well-quasi-ordering of graphs under strong immersions and a conjecture relating the chromatic number of a graph and the exclusion of a clique immersion.