$K_4$-Minor-Free Induced Subgraphs of Sparse Connected Graphs

Abstract

We prove that every connected graph $G$ with $m$ edges contains a set $X$ of at most $\frac{3}{16}(m+1)$ vertices such that $G-X$ has no $K_4$ minor, or equivalently, has treewidth at most $2$. This bound is best possible. Connectivity is essential: If $G$ is not connected then only a bound of $\frac{1}{5}m$ can be guaranteed.

References in corpus (1)

• Planar Induced Subgraphs of Sparse Graphs