簇状独立和有界树宽 (Clustered independence and bounded treewidth)

A set $S\subseteq V$ of vertices of a graph $G$ is a \emph{$c$-clustered set} if it induces a subgraph with components of order at most $c$ each, and $\alpha_c(G)$ denotes the size of a largest $c$-clustered set. For any graph $G$ on $n$ vertices and treewidth $k$, we show that $\alpha_c(G) \geq \frac{c}{c+k+1}n$, which improves a result of Wood [arXiv:2208.10074, August 2022], while we construct $n$-vertex graphs $G$ of treewidth~$k$ with $\alpha_c(G)\leq \frac{c}{c+k}n$. In the case $c\leq 2$ or $k=1$ we prove the better lower bound $\alpha_c(G) \geq \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 $\alpha_c(G) \geq \frac{5}{9}n$ and which is best-possible.

翻译：摘要：设$S\subseteq V$ 是图$G$的一组顶点，若它诱导的子图中每个连通分量都有不超过$c$个顶点，则称其为\emph{$c$-簇状集合}，$\alpha_c(G)$表示最大$c$-簇状集合的大小。对于任意$n$个顶点和树宽$k$的图$G$，我们证明了$\alpha_c(G) \geq \frac{c}{c+k+1}n$，这改进了Wood的结果[arXiv:2208.10074，2022年8月]，同时我们构造了一个包含$n$个顶点且树宽为$k$的图$G$，其中$\alpha_c(G) \leq \frac{c}{c+k}n$。在$c\leq 2$或$k=1$的情况下，我们证明了更好的下界$\alpha_c(G)\geq\frac{c}{c+k}n$，并推广了Chappell和Pelsmajer的猜想[Electron.J.Comb.，2013]，该猜想是最优选择的。最后，在$c=3$且$k=2$的情况下，我们证明了$\alpha_c(G) \geq \frac{5}{9}n$，这是最优选择的。