2023/03/23 by Knauer, Kolja, Ueckerdt, Torsten · 1 citation
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2303.13655
A set S⊆ 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) ≥ (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 αc(G)≤ (c)/(c+k)n. In the case c≤ 2 or k=1 we prove the better lower bound αc(G) ≥ (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) ≥ (5)/(9)n and which is best-possible.