Gwenaël Joret, Packing and covering balls in graphs excluding a minor

In 2007, Chepoi, Estellon, and Vaxès conjectured that there exists a universal constant $c>0$ such that the following holds for every positive integers $r$ and $k$, and every planar graph $G$: Either $G$ contains $k$ vertex-disjoint balls of radius $r$, or there is a subset of vertices of size at most $c k$ meeting all balls of radius $r$ in $G$. The key aspect of this conjecture is that the constant $c$ does not depend on the radius $r$ of the balls. If we were to allow this dependency, then the statement is known to hold, and in fact it is true in the more general setting of graph classes with bounded expansion (as proved by Dvořák).

In this talk I will present a proof of this conjecture. The result we prove is a bit more general: (1) The conjecture holds for every proper minor-closed class of graphs (with the constant $c$ depending on the class), and (2) we can even focus on any set of balls in the graph we like, there is nothing special about taking all balls of a given radius. In other words, we show that for every proper minor-closed class $C$ of graphs, there exists a constant $c>0$ such that for every graph $G$ in $C$, every set $S$ of balls in $G$, and every positive integer $k$, either there are $k$ vertex-disjoint balls in $S$, or there is a subset of vertices of $G$ of size at most $c k$ meeting all balls in $S$.

Joint work with Nicolas Bousquet, Wouter Cames van Batenburg, Louis
Esperet, William Lochet, Carole Muller, and François Pirot.