pith. sign in

arxiv: 1510.03041 · v3 · pith:PVM2LYR6new · submitted 2015-10-11 · 🧮 math.CO · cs.DS

Minors in graphs of large {θ}_r-girth

classification 🧮 math.CO cs.DS
keywords girththetagraphslargeminimumcasedegreeedges
0
0 comments X
read the original abstract

For every $r \in \mathbb{N}$, let $\theta_r$ denote the graph with two vertices and $r$ parallel edges. The $\theta_r$-girth of a graph $G$ is the minimum number of edges of a subgraph of $G$ that can be contracted to $\theta_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\"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 $\theta_{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$ $\theta_{r}$'s have treewidth $O(k\cdot \log k)$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.