2014/12/04 by Nicolás Bousquet, Bousquet, Nicolas, Stéphan Thomassé +1 · 3 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Digital Image Processing Techniques #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1412.1793
openalex publication_date 2014/12/04 · openalex created_date 2021/05/24 · openalex updated_date 2026/07/28
Let G=(V,E) be a graph. A k-neighborhood in G is a set of vertices consisting of all the vertices at distance at most k from some vertex of G. The hypergraph on vertex set V which edge set consists of all the k-neighborhoods of G for all k is the neighborhood hypergraph of G. 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 G as the maximum taken over all induced subgraphs G' of G of the VC-dimension of the neighborhood hypergraph of 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, Estellon and Vaxès asserting that every planar graph of diameter 2ℓ can be covered by a bounded number of balls of radius ℓ. In fact, they obtained the existence of a function f such that every set \cal F of balls of radius ℓ in a planar graph admits a hitting set of size f(ν) where ν is the maximum number of pairwise disjoint elements of \cal F. Our goal is to generalize the proof of Chepoi, Estellon and Vaxès 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.