Graphs and Matroids Seminar - Louis Esperet

Title: Packing and covering balls in planar graphs

Abstract:

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.