- Graph Theory Seminar
- Thursday, August 30, 2018 - 12:00 for 1 hour (actually 50 minutes)
- Skiles 005
- 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.