Back to Search
Start Over
Minors in graphs of large $��_r$-girth
- Publication Year :
- 2015
- Publisher :
- arXiv, 2015.
-
Abstract
- For every $r \in \mathbb{N}$, let $��_r$ denote the graph with two vertices and $r$ parallel edges. The $��_r$-girth of a graph $G$ is the minimum number of edges of a subgraph of $G$ that can be contracted to $��_r$. This notion generalizes the usual concept of girth which corresponds to the case $r=2$. In [Minors in graphs of large girth, Random Structures & Algorithms, 22(2):213--225, 2003], K��hn 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 $��_{r}$-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 $r$, graphs excluding as a minor the disjoint union of $k$ $��_{r}$'s have treewidth $O(k\cdot \log k)$.<br />Some of the results of this paper have been presented in WAOA 2015
Details
- Database :
- OpenAIRE
- Accession number :
- edsair.doi...........bc1bd8ddae407b0e4a19ef88605ab682
- Full Text :
- https://doi.org/10.48550/arxiv.1510.03041