EUVIMEDEUVIMED entdecken
Crossref

Clustered Independence and Bounded Treewidth

Kolja Knauer, Torsten Ueckerdt

The Electronic Journal of Combinatorics · 19.06.2026 · 33 (2)

DOI: 10.37236/12247 ↗

Kurz gefasst

Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 19.06.2026. Verfasst von Kolja Knauer und 1 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 $\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 Dvořák and Wood [Innov. Graph Theory, 2025], 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$ which is best-possible.

Zitieren

APA

Knauer, K., & Ueckerdt, T. (2026). Clustered Independence and Bounded Treewidth. The Electronic Journal of Combinatorics, 33(2). https://doi.org/10.37236/12247

Vancouver

Knauer K, Ueckerdt T. Clustered Independence and Bounded Treewidth. The Electronic Journal of Combinatorics. 2026;33(2). doi:10.37236/12247

BibTeX
@article{Knauer2026,
  author = {Knauer, Kolja and Ueckerdt, Torsten},
  title = {Clustered Independence and Bounded Treewidth},
  journal = {The Electronic Journal of Combinatorics},
  year = {2026},
  volume = {33},
  number = {2},
  doi = {10.37236/12247}
}
Kostenlos starten →