
arXiv: 2405.13797
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.
16 pages, 3 figures
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), 05C99, 05C69, sparsity, induced subgraphs, Trees, Computer Science - Data Structures and Algorithms, Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.), treewidth, FOS: Mathematics, Mathematics - Combinatorics, Density (toughness, etc.), Data Structures and Algorithms (cs.DS), Combinatorics (math.CO), F.2.2, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), 05C99, 05C69, sparsity, induced subgraphs, Trees, Computer Science - Data Structures and Algorithms, Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.), treewidth, FOS: Mathematics, Mathematics - Combinatorics, Density (toughness, etc.), Data Structures and Algorithms (cs.DS), Combinatorics (math.CO), F.2.2, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
