





















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 $Δ$. As an application, we obtain the following result: Let $G$ be a claw-free graph with maximum degree at most $Δ$. Then, every collection of $\left\lfloor\left(\fracΔ{2}+1\right)(n-1)\right\rfloor+1$ independent sets in $G$ has a rainbow independent set of size $n$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。