Atlantic Graph Theory Seminar
February 25, 2026 @ 3:30 pm - 4:30 pm
Date and Time: Wednesday, February 25, 3.40 pm Atlantic time
Speaker: Erin Meger, Queens University
Title: Decomposing Forbidden Minors for Pursuit-Evasion
Abstract: In this talk, we consider the pursuit-evasion game Cops and Robbers. The game is played on a graph between two players: a set of cops and a single robber, who take turns moving along the edges. The cop number of a graph is the minimum number of cops needed to guarantee capture of the robber, meaning they eventually occupy the same vertex. It is standard to consider classes of graphs defined by forbidden substructures such as minors or induced subgraphs. A graph G is H-free or H-minor free if G does not contain, respectively, any induced subgraph or minor which is isomorphic to H.
The role of forbidden minors in pursuit-evasion began in Andrae’s work in 1986. For graphs that exclude a fixed minor H, the upper bound for the cop-number is nearly the number of edges in this forbidden minor. When the minor has restricted structure, we can reduce this upper bound. In this talk, I focus on the cop-strategy to build a copy of the minor that is forbidden, and show how we can guarantee capture due to this underlying structure.
Zoom link:
Meeting ID: 880 1326 1876
Passcode: 357963