Packing and covering balls in planar graphs

Speaker: François Pirot (GSCOP)

Abstract: In a graph {$G$}, the packing number {$ν_r(G) $} of balls of radius r is the size of a maximum set of pairwise disjoint balls of radius {$r$} (which is then an independent set in {$ G^{2r} $}) and the covering number {$τ_r(G)$} of balls of radius {$r$} is the minimum size of a set of balls of radius {$r$} whose union contains all vertices of {$G$} (it is then a dominating set of {$G^r$}). These two parameters are dual and in general they can be arbitrarily different. Bousquet and Thomassé proved in 2015 that in planar graphs, {$τ_r(G)$} is always bounded from above by a polynomial function of {$ν_r(G)$} (independently of {$r$}) via a VC-dimension argument. The goal of this talk is to show that this upper-bound is actually linear, which solves a conjecture of Chepoi, Estellon and Vaxès of 2007. (Joint work with Nicolas Bousquet, Wouter Cames van Batenburg, Louis Esperet, Gwenaël Joret, William Lochet et Carole Muller).

Date and time: 04/05/2020 at 14:30

Recorded talk: https://visio.u-bordeaux.fr/playback/presentation/2.0/playback.html?meetingId=2300964ed37832030257d03332f1e49dfb29c699-1588855237838