Back to Search Start Over

Minors in graphs of large $��_r$-girth

Authors :
Chatzidimitriou, Dimitris
Raymond, Jean-Florent
Sau, Ignasi
Thilikos, Dimitrios M.
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