Sparse Induced Subgraphs of Large Treewidth

Autor:	Bonnet, Édouard
Rok vydání:	2024
Předmět:	Mathematics - Combinatorics Computer Science - Discrete Mathematics Computer Science - Data Structures and Algorithms 05C99 05C69 F.2.2
Druh dokumentu:	Working Paper
Popis:	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 $\varepsilon > 0$, there is an integer $W := W(t,w,\varepsilon)$ 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+\varepsilon)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. Comment: 16 pages, 3 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2405.13797 Zobrazit plný text záznamu View this record from Arxiv