2015/10/11 by Dimitris Chatzidimitriou, Jean‐Florent Raymond, Chatzidimitriou, Dimitris +5
Computer Science · #05C35 #05C83 #05C85 #68R10 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1510.03041
openalex publication_date 2015/10/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For every r \∈ \ℕ, let \θr denote the graph with two\nvertices and r parallel edges. The \θr-girth of a graph G is the\nminimum number of edges of a subgraph of G that can be contracted to\n\θr. This notion generalizes the usual concept of girth which\ncorresponds to the case r=2. In [Minors in graphs of large girth, Random\nStructures & Algorithms, 22(2):213--225, 2003], K "uhn and Osthus showed that\ngraphs of sufficiently large minimum degree contain clique-minors whose order\nis an exponential function of their girth. We extend this result for the case\nof \θr-girth and we show that the minimum degree can be replaced by\nsome connectivity measurement. As an application of our results, we prove that,\nfor every fixed r, graphs excluding as a minor the disjoint union of k\n\θr's have treewidth O(k\⋅ \log k).\n