Sparse Induced Subgraphs of Large Treewidth
<|reference_start|>Sparse Induced Subgraphs of Large Treewidth: 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.<|reference_end|>
@article{bonnet2024sparse,
    title={Sparse Induced Subgraphs of Large Treewidth},
    author={'Edouard Bonnet},
    journal={arXiv preprint arXiv:2405.13797},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.13797},
    primaryClass={math.CO cs.DM cs.DS}
}