VC-dimension and Erdős-Pósa property
作者： Nicolas Bousquet , Stéphan Thomassé
DOI: 10.1016/J.DISC.2015.05.026
关键词:
摘要: Let G = ( V , E ) be a graph. A k -neighborhood in is set of vertices consisting all the at distance most from some vertex . The hypergraph on whose edge consists -neighborhoods for neighborhood Our goal this paper to investigate complexity graph terms its neighborhoods. Precisely, we define VC-dimension as maximum taken over induced subgraphs ' For class graphs, having bounded both generalizes minor closed classes and graphs with clique-width.Our motivation result Chepoi et?al. (2007) asserting that every planar diameter 2 ? can covered by number balls radius In fact, they obtained existence function f such F admits hitting size where pairwise disjoint elements .Our generalize proof unique assumption other words, fixed has Erd?s-Posa property.
archives-ouvertes.fr
acm.org
elsevier.com
sci-hub.se 参考文章(20)
Noga Alon, Daniel J Kleitman, Piercing convex sets and the Hadwiger-Debrunner (p, q)-problem Advances in Mathematics. ,vol. 96, pp. 103- 112 ,(1992) , 10.1016/0001-8708(92)90052-M
Bernard Chazelle, Emo Welzl, Quasi-optimal range searching in spaces of finite VC-dimension Discrete & Computational Geometry. ,vol. 4, pp. 467- 489 ,(1989) , 10.1007/BF02187743
V. N. Vapnik, A. Ya. Chervonenkis, On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities Measures of Complexity. ,vol. 16, pp. 11- 30 ,(2015) , 10.1007/978-3-319-21852-6_3
D Haussler, E Welzl, Epsilon-nets and simplex range queries Proceedings of the second annual symposium on Computational geometry - SCG '86. pp. 61- 71 ,(1986) , 10.1145/10515.10522
Sang-il Oum, Paul Seymour, Approximating clique-width and branch-width Journal of Combinatorial Theory, Series B. ,vol. 96, pp. 514- 528 ,(2006) , 10.1016/J.JCTB.2005.10.006
Zdeněk Dvořák, Constant-factor approximation of the domination number in sparse graphs The Journal of Combinatorics. ,vol. 34, pp. 833- 840 ,(2013) , 10.1016/J.EJC.2012.12.004
Noga Alon, Graham Brightwell, H.A. Kierstead, A.V. Kostochka, Peter Winkler, Dominating sets in k -majority tournaments Journal of Combinatorial Theory, Series B. ,vol. 96, pp. 374- 387 ,(2006) , 10.1016/J.JCTB.2005.09.003
Paul Erdös, Graph Theory and Probability Canadian Journal of Mathematics. ,vol. 11, pp. 276- 280 ,(1959) , 10.1007/978-0-8176-4842-8_19
Patrick Assouad, Densité et dimension Annales de l’institut Fourier. ,vol. 33, pp. 233- 282 ,(1983) , 10.5802/AIF.938
L Pósa, None, On independent circuits contained in a graph Canadian Journal of Mathematics. ,vol. 17, pp. 347- 352 ,(1965) , 10.4153/CJM-1965-035-8