TY - JOUR
T1 - Minors in graphs of large θr-girth
AU - Chatzidimitriou, Dimitris
AU - Raymond, Jean Florent
AU - Sau, Ignasi
AU - Thilikos, Dimitrios M.
N1 - Publisher Copyright:
© 2017 Elsevier Ltd
PY - 2017/10
Y1 - 2017/10
N2 - For every r∈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 Kühn and Osthus (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⋅logk).
AB - For every r∈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 Kühn and Osthus (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⋅logk).
UR - http://www.scopus.com/inward/record.url?scp=85020433383&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85020433383&partnerID=8YFLogxK
U2 - 10.1016/j.ejc.2017.04.011
DO - 10.1016/j.ejc.2017.04.011
M3 - Article
AN - SCOPUS:85020433383
SN - 0195-6698
VL - 65
SP - 106
EP - 121
JO - European Journal of Combinatorics
JF - European Journal of Combinatorics
ER -