Georgia Institute of Technology College of Sciences

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.