Minors in graphs of large _r-girth
From MaRDI portal
Publication:2400974
DOI10.1016/J.EJC.2017.04.011zbMATH Open1369.05187arXiv1510.03041OpenAlexW2405772563MaRDI QIDQ2400974FDOQ2400974
Authors: Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau, Dimitrios M. Thilikos 
Publication date: 31 August 2017
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Abstract: For every , let denote the graph with two vertices and parallel edges. The -girth of a graph is the minimum number of edges of a subgraph of that can be contracted to . This notion generalizes the usual concept of girth which corresponds to the case . In [Minors in graphs of large girth, Random Structures & Algorithms, 22(2):213--225, 2003], K"uhn and Osthus showed that graphs of sufficiently large minimum degree contain clique-minors whose order is an exponential function of their girth. We extend this result for the case of -girth and we show that the minimum degree can be replaced by some connectivity measurement. As an application of our results, we prove that, for every fixed , graphs excluding as a minor the disjoint union of 's have treewidth .
Full work available at URL: https://arxiv.org/abs/1510.03041
Recommendations
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph minors (05C83)
Cites Work
- Graph minors. X: Obstructions to tree-decomposition
- Title not available (Why is that?)
- The extremal function for complete minors
- An extremal function for contractions of graphs
- Lower bound of the Hadwiger number of graphs by their average degree
- Graph minors. V. Excluding a planar graph
- Highly connected sets and the excluded grid theorem
- Quickly excluding a planar graph
- Minors in random regular graphs
- (Meta) Kernelization
- Quadratic upper bounds on the Erdős--Pósa property for a generalization of packing and covering cycles
- Brambles, prisms and grids
- Polynomial bounds for the grid-minor theorem
- Large-treewidth graph decompositions and applications
- On Linear Time Minor Tests with Depth-First Search
- Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
- Isomorphism for graphs of bounded distance width
- Excluded grid theorem: improved and simplified
- Topics in Matroid Theory
- A Linear-Time Algorithm for Finding a Complete Graph Minor in a Dense Graph
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the excluded minors for the matroids of branch-width \(k\)
- The branchwidth of graphs and their cycle matroids
- Girth and treewidth
- Minors in graphs of large girth
- Complete minors in cubic graphs with few short cycles and random cubic graphs.
- Tree-partitions of infinite graphs
- Complete minors in \(K_{s,s}\)-free graphs
- New spectral lower bounds on the bisection width of graphs
- On tree-partitions of graphs
- On interval routing schemes and treewidth
- Complete graph minors and the graph minor structure theorem
- Low polynomial exclusion of planar graph patterns
Cited In (13)
- Minors in graphs of large girth
- A note on graphs with large girth and small minus domination number
- Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
- Graph Minors I: A Short Proof of the Path-width Theorem
- An \(O(\log \mathrm{OPT})\)-approximation for covering and packing minor models of \(\theta _r\)
- Excluding a large theta graph
- Small complete minors above the extremal edge density
- Packing and covering immersion-expansions of planar sub-cubic graphs
- Dense minors in graphs of large girth
- High-girth graphs avoiding a minor are nearly bipartite
- Unavoidable minors for graphs with large \(\ell_p\)-dimension
- Lean Tree-Cut Decompositions: Obstructions and Algorithms
- Girth and treewidth
This page was built for publication: Minors in graphs of large \(\theta_r\)-girth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2400974)
