Packing and covering balls in graphs excluding a minor

01/13/2020
by   Nicolas Bousquet, et al.
0

We prove that for every integer t> 1 there exists a constant c_t such that for every K_t-minor-free graph G, and every set S of balls in G, the minimum size of a set of vertices of G intersecting all the balls of S is at most c_t times the maximum number of vertex-disjoint balls in S. This was conjectured by Chepoi, Estellon, and Vaxès in 2007 in the special case of planar graphs and of balls having the same radius.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset