Clustered independence and bounded treewidth

Abstract

A set $S\subseteq V$ of vertices of a graph $G$ is a $c$-clustered set if it induces a subgraph with components of order at most $c$ each, and $\hat{I}{\pm }_c(G)$ denotes the size of a largest $c$-clustered set. For any graph $G$ on $n$ vertices and treewidth $k$, we show that $\hat{I}{\pm }_c(G)\ge \frac{c}{c+k+1}n$, which improves a result of Dvoř{á}k and Wood [Innov.\ Graph Theory, 2025], while we construct $n$-vertex graphs $G$ of treewidth $k$ with $\hat{I}{\pm }_c(G)\le \frac{c}{c+k}n$. In the case $c\le 2$ or $k=1$ we prove the better lower bound $\hat{I}{\pm }_c(G)\ge \frac{c}{c+k}n$, which settles a conjecture of Chappell and Pelsmajer [Electron.\ J.\ Comb., 2013] and is best-possible. Finally, in the case $c=3$ and $k=2$, we show $\hat{I}{\pm }_c(G)\ge \frac{5}{9}n$ which is best-possible.

16 pages, 6 figures