Random Graphs with Few Disjoint Cycles
- 1 January 2011
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 20 (5) , 763-775
Abstract
The classical Erdős–Pó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ős–Pósa theorem with the extra ‘redundancy’ property that B–v is still a blocker for all but at most k vertices v ∈ B.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Random graphs containing few disjoint excluded minorsRandom Structures & Algorithms, 2012
- Random unlabelled graphs containing few disjoint cyclesRandom Structures & Algorithms, 2010
- Random Graphs from a Minor-Closed ClassCombinatorics, Probability and Computing, 2009
- Analytic Combinatorics2009
- Random Graphs from Planar and Other Addable Classes2007
- Random planar graphsJournal of Combinatorial Theory, Series B, 2005
- Packing directed circuitsCombinatorica, 1996
- Graph minors. V. Excluding a planar graphJournal of Combinatorial Theory, Series B, 1986
- Chromatic Number and Topological Complete SubgraphsCanadian Mathematical Bulletin, 1965
- On Independent Circuits Contained in a GraphCanadian Journal of Mathematics, 1965