VC-dimension and Erdős-Pósa property
From MaRDI portal
Publication:2515568
DOI10.1016/j.disc.2015.05.026zbMath1318.05050arXiv1412.1793OpenAlexW581283990MaRDI QIDQ2515568
Nicolas Bousquet, Steéphan Thomassé
Publication date: 5 August 2015
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1412.1793
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (16)
Packing and covering with balls on Busemann surfaces ⋮ Vapnik-Chervonenkis dimension and density on Johnson and Hamming graphs ⋮ Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension ⋮ Recent techniques and results on the Erdős-Pósa property ⋮ Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs ⋮ Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs ⋮ Erdös-Pósa Property of Obstructions to Interval Graphs ⋮ Beyond Helly graphs: the diameter problem on absolute retracts ⋮ Sample Compression Schemes for Balls in Graphs ⋮ A story of diameter, radius, and (almost) Helly property ⋮ Erdős–Pósa property of obstructions to interval graphs ⋮ Parameterized and approximation complexity of \textsc{Partial VC Dimension} ⋮ Bounding the Order of a Graph Using Its Diameter and Metric Dimension: A Study Through Tree Decompositions and VC Dimension ⋮ On the VC-dimension, covering and separating properties of the cycle and spanning tree hypergraphs of graphs ⋮ Packing and covering balls in graphs excluding a minor ⋮ On density of subgraphs of halved cubes
Cites Work
- Unnamed Item
- Classes of graphs with small rank decompositions are \(\chi \)-bounded
- Covering planar graphs with a fixed number of balls
- Piercing convex sets and the Hadwiger-Debrunner \((p,q)\)-problem
- Bounding the vertex cover number of a hypergraph
- Quasi-optimal range searching in spaces of finite VC-dimension
- Density and dimension
- Bounded VC-dimension implies a fractional Helly theorem
- Constant-factor approximation of the domination number in sparse graphs
- Dominating sets in \(k\)-majority tournaments.
- Approximating clique-width and branch-width
- On the density of families of sets
- Graph Theory and Probability
- Domination in planar graphs with small diameter*
- Domination numbers of planar graphs
- On Independent Circuits Contained in a Graph
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
This page was built for publication: VC-dimension and Erdős-Pósa property
