Vertex-minors and immersions

Vertex-minors and immersions

-
Rose McCarty, University of Waterloo

The vertex-minors of a graph G are the graphs that can be obtained from G using two operations: 1) deleting a vertex and 2) replacing the induced subgraph on the neighborhood of a vertex by its complement. This second operation gives a good deal of freedom, and we conjecture that there is a nice structural description of graph classes that exclude a vertex-minor. We discuss how to understand the ''local structure'' via a connection with immersion minors. This is perhaps surprising since classes that exclude a vertex-minor are usually dense (i.e. contain all bicliques), while classes that exclude an immersion minor must be sparse. 

This is joint work with Jim Geelen and Paul Wollan.