Online Talk: Louis Esperet

Tuesday, March 1, 11am ET (4pm GMT, 5am Wed NZDT)
Louis Esperet, G-SCOP Laboratory (CNRS, Grenoble)
Packing and covering balls in planar graphs

The set of all vertices at distance at most $r$ from a vertex $v$ in a graph $G$ is called an $r$-ball. We prove that the minimum number of vertices hitting all $r$-balls in a planar graph $G$ is at most a constant (independent of $r$) times the maximum number of vertex-disjoint $r$-balls in $G$. This was conjectured by Estellon, Chepoi and Vaxès in 2007. Our result holds more generally for any proper minor-closed class, and for systems of balls of arbitrary (and possibly distinct) radii.
Joint work with N. Bousquet, W. Cames van Batenburg, G. Joret, W. Lochet, C. Muller, and F. Pirot.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.