Random graphs with few disjoint cycles

DOI10.1017/S0963548311000186MaRDI QIDQ3103626zbMATH OpenOpenAlexFDO

Authors Valentas Kurauskas, Colin McDiarmid

Publication date 8 December 2011

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1010.6278

zbMATH Keywords

blockerchromatic numberclique numberconnectivitydisjoint cyclesforestrandom graph

Mathematics Subject Classification ID

Paths and cycles (05C38) Connectivity (05C40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Random graphs (graph-theoretic aspects) (05C80)

Abstract: The classical ErdH{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 ErdH{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.

Recommendations

• Random unlabelled graphs containing few disjoint cycles
• Random graphs containing few disjoint excluded minors
• Disjoint cycles intersecting a set of vertices
• The Erdős-Pósa property for odd cycles in highly connected graphs
• A tight Erdős-Pósa function for long cycles

Cites work

• Chromatic Number and Topological Complete Subgraphs
• Graph minors. V. Excluding a planar graph
• scientific article; zbMATH DE number 487720 (Why is no real title available?)
• On Independent Circuits Contained in a Graph
• Packing directed circuits
• Random graphs from a minor-closed class
• Random planar graphs
• Random unlabelled graphs containing few disjoint cycles

Cited in

(11)

• Graphs that are randomly packable by some common disconnected graphs
• Random cyclic triangle-free graphs of prime order
• Maximum degree in minor-closed classes of graphs
• Random unlabelled graphs containing few disjoint cycles
• Random graphs from a weighted minor-closed class
• scientific article; zbMATH DE number 1750092 (Why is no real title available?)
• Cycles and Unicyclic Components in Random Graphs
• Subcritical graph classes containing all planar graphs
• Random graphs containing few disjoint excluded minors
• On graphs with few disjoint \(t\)-star minors
• Random graphs from a block-stable class

This page was built for publication: Random graphs with few disjoint cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3103626)