Complexes of graphs with bounded independence number

Abstract

Let $G=(V,E)$ be a graph and $n$ a positive integer. Let $I_n(G)$ be the abstract simplicial complex whose simplices are the subsets of $V$ that do not contain an independent set of size $n$ in $G$. We study the collapsibility numbers of the complexes $I_n(G)$ for various classes of graphs, focusing on the class of graphs with maximum degree bounded by $\Delta$. As an application, we obtain the following result: Let $G$ be a claw-free graph with maximum degree at most $\Delta$. Then, every collection of $\lfloor \left(\frac{\Delta }{2}+1\right)(n-1)\rfloor +1$ independent sets in $G$ has a rainbow independent set of size $n$.

References in corpus (1)

• Rainbow fractional matchings

Cited by in corpus (3)

• Rainbow independent sets on dense graph classes
• A system of disjoint representatives of line segments with given $k$ directions
• Leray numbers of tolerance complexes