J. Pascal Gollin, Dominated balanced separators in wheel-induced-minor-free graphs

The grid theorem of Robertson and Seymour can be equivalently stated using balanced separators, that are separators whose deletion leaves every component with no more than half of the vertices of the graph, as follows. Every graph that excludes some planar graph as a minor has a balanced separator of bounded size. Building on this formulation, Gartland and Lokshtanov conjectured an induced minor version of that theorem inspired by coarse graph theory. They conjectured that every graph that excludes some planar graph as an induced minor has a balanced separator which is dominated by a bounded number of vertices. We confirm this conjecture for excluding any fixed wheel, that is, a cycle together with a universal vertex, as an induced minor.

This talk is based on joint work with Maria Chudnovsky, Matjaž Krnc, and Martin Milanič.