Graphs and Matroids Seminar - Louis Esperet

Tuesday, March 1, 2022 11:00 am - 11:00 am EST (GMT -05:00)

Title: Packing and covering balls in planar graphs

Speaker: Louis Esperet
Affiliation: G-SCOP Laboratory
Zoom: Join via or please email Shayla Redlin


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.