Sparse Induced Subgraphs of Large Treewidth

2024/05/22 by Bonnet, Édouard · 2 citations
#05C69 #05C99 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2405.13797

Abstract

Motivated by an induced counterpart of treewidth sparsifiers (i.e., sparse subgraphs keeping the treewidth large) provided by the celebrated Grid Minor theorem of Robertson and Seymour [JCTB '86] or by a classic result of Chekuri and Chuzhoy [SODA '15], we show that for any natural numbers t and w, and real ε > 0, there is an integer W := W(t,w,ε) such that every graph with treewidth at least W and no K_t,t subgraph admits a 2-connected n-vertex induced subgraph with treewidth at least w and at most (1+ε)n edges. The induced subgraph is either a subdivided wall, or its line graph, or a spanning supergraph of a subdivided biclique. This in particular extends a result of Weissauer [JCTB '19] that graphs of large treewidth have a large biclique subgraph or a long induced cycle.

Cited by

• Coloring Hardness on Low Twin-Width Graphs
• Excluding a Forest Induced Minor

Related

• Induced subgraphs and tree decompositions V. Small components of big vertices
• Induced subgraphs and tree decompositions V. one neighbor in a hole
• Treewidth is Polynomial in Maximum Degree on Weakly Sparse Graphs Excluding a Planar Induced Minor
• Induced subgraphs and path decompositions
• Induced subgraphs and tree decompositions XVIII. Obstructions to bounded pathwidth