Clustered independence and bounded treewidth
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917512271101952 |
|---|---|
| author | Knauer, Kolja Ueckerdt, Torsten |
| author_facet | Knauer, Kolja Ueckerdt, Torsten |
| contents | 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 $α_c(G)$ denotes the size of a largest $c$-clustered set. For any graph $G$ on $n$ vertices and treewidth $k$, we show that $α_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 $α_c(G)\leq \frac{c}{c+k}n$. In the case $c\leq 2$ or $k=1$ we prove the better lower bound $α_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 $α_c(G) \geq \frac{5}{9}n$ which is best-possible. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_13655 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Clustered independence and bounded treewidth Knauer, Kolja Ueckerdt, Torsten Combinatorics Discrete Mathematics 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 $α_c(G)$ denotes the size of a largest $c$-clustered set. For any graph $G$ on $n$ vertices and treewidth $k$, we show that $α_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 $α_c(G)\leq \frac{c}{c+k}n$. In the case $c\leq 2$ or $k=1$ we prove the better lower bound $α_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 $α_c(G) \geq \frac{5}{9}n$ which is best-possible. |
| title | Clustered independence and bounded treewidth |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2303.13655 |