Clustered independence and bounded treewidth

Abstract: A set

S s u b s e t e q 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

a l p h a_{c} (G)

denotes the size of a largest

c

-clustered set. For any graph

G

on

n

vertices and treewidth

k

, we show that

a l p h a_{c} (G) g e q f r a c 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

a l p h a_{c} (G) l e q f r a c c c + k n

. In the case

c l e q 2

or

k = 1

we prove the better lower bound

a l p h a_{c} (G) g e q f r a c 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

a l p h a_{c} (G) g e q f r a c 59 n

and which is best-possible.

This page was built for publication: Clustered independence and bounded treewidth