The Grid Theorem for Vertex Minors

Series
Graph Theory Seminar
Time
Thursday, August 30, 2018 - 12:00pm for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Rose McCarty – University of Waterloo
Organizer
Robin Thomas
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.