### The Grid Theorem for Vertex Minors

- Series
- Graph Theory Seminar
- Time
- Thursday, August 30, 2018 - 12:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Rose McCarty – University of Waterloo

Vertex minors are a weakening of the notion of induced subgraphs that
benefit from many additional nice properties. In particular, there is a
vertex minor version of Menger's Theorem proven by Oum. This theorem
gives rise to a natural analog of branch-width called rank-width.
Similarly to the Grid Theorem of Robertson and Seymour, we prove that a
class of graphs has unbounded rank-width if and only if it contains all
"comparability grids'' as vertex minors. This is joint work with Jim
Geelen, O-joung Kwon, and Paul Wollan.