Name
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1017/S0963548311000186 | Combinatorics, Probability & Computing |
Keywords | Field | DocType |
random graph,k vertices v,chromatic number,clique number,classical erd,size k,graph g,disjoint cycle,sa theorem,main theorem,sa theorem state,positive integer k | Perfect graph,Discrete mathematics,Random regular graph,Combinatorics,Graph toughness,Random graph,Disjoint sets,Clique graph,Clique-sum,Independent set,Mathematics | Journal |
Volume | Issue | ISSN |
20 | 5 | Combinatorics, Probability and Computing 20 (2011) 763 -- 775 |
Citations | PageRank | References |
4 | 0.45 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Valentas Kurauskas | 1 | 29 | 4.00 |
| Colin McDiarmid | 2 | 1071 | 167.05 |