arXiv FOCS 2026 | tags:[ graph theory ]
A Coarse Menger's Theorem for Planar and Bounded Genus Graphs
with Michał Pilipczuk and Evangelos ProtopapasMenger’s Theorem says that if a graph $G$ with terminal sets $S$ and $T$ has no $k$ pairwise vertex-disjoint $S$-$T$ paths, then some set of fewer than $k$ vertices intersects every $S$-$T$ path.
We give a coarse variant of this for planar and bounded-genus graphs: for every surface $\Sigma$ there is a function $f \colon \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ such that for every $d, k \in \mathbb{N}$ and every $\Sigma$-embeddable graph $G$ with terminal sets $S, T$, if $G$ has no $k$ $S$-$T$ paths that are pairwise at distance more than $d$, then there is a set $X$ of at most $f(d,k)$ vertices such that every $S$-$T$ path passes within distance $d$ of $X$. This partially answers a question of Nguyen, Scott, and Seymour, who showed that no such statement can hold for general graphs. A key ingredient is a structure theorem from the developing “colorful” graph minor theory, which studies the structure of a graph relative to fixed subsets of annotated vertices – here, $S$ and $T$.