Author
Kurauskas, V
McDiarmid, C
Journal title
Combinatorics, Probability and Computing
Volume
20
Last updated
2021-11-11T17:37:24.463+00:00
Page
763-775
Abstract
The classical Erd\H{o}s-P\'{o}sa theorem states that for each positive
integer k there is an f(k) such that, in each graph G which does not have k+1
disjoint cycles, there is a blocker of size at most f(k); that is, a set B of
at most f(k) vertices such that G-B has no cycles. We show that, amongst all
such graphs on vertex set {1,..,n}, all but an exponentially small proportion
have a blocker of size k. We also give further properties of a random graph
sampled uniformly from this class; concerning uniqueness of the blocker,
connectivity, chromatic number and clique number. A key step in the proof of
the main theorem is to show that there must be a blocker as in the
Erd\H{o}s-P\'{o}sa theorem with the extra `redundancy' property that B-v is
still a blocker for all but at most k vertices v in B.
Symplectic ID
102316
Download URL
http://arxiv.org/abs/1010.6278v1
Publication type
Journal Article
Please contact us with feedback and comments about this page. Created on 13 Oct 2016 - 17:14.