VC-dimension and Erdős–Pósa property

Let G=(V,E)G=(V,E) be a graph. A kk-neighborhood   in GG is a set of vertices consisting of all the vertices at distance at most kk from some vertex of GG. The hypergraph on vertex set VV whose edge set consists of all the kk-neighborhoods of GG for all kk is the neighborhood hypergraph   of GG. Our goal in this paper is to investigate the complexity of a graph in terms of its neighborhoods. Precisely, we define the distance VC-dimension   of a graph GG as the maximum taken over all induced subgraphs G′G′ of GG of the VC-dimension of the neighborhood hypergraph of G′G′. For a class of graphs, having bounded distance VC-dimension both generalizes minor closed classes and graphs with bounded clique-width.Our motivation is a result of Chepoi et al. (2007) asserting that every planar graph of diameter 2ℓ2ℓ can be covered by a bounded number of balls of radius ℓℓ. In fact, they obtained the existence of a function ff such that every set FF of balls of radius ℓℓ in a planar graph admits a hitting set of size f(ν)f(ν) where νν is the maximum number of pairwise disjoint elements of FF.Our goal is to generalize the proof of Chepoi et al. (2007) with the unique assumption of bounded distance VC-dimension of neighborhoods. In other words, the set of balls of fixed radius in a graph with bounded distance VC-dimension has the Erdős–Pósa property.