Collapsibility of noncover complexes of chordal graphs

Abstract

Let $G$ be a graph on $V$. A vertex subset $S\subset V$ is called a cover of $G$ if its complement is an independent set, and $S$ is called a noncover if it is not a cover of $G$. A noncover complex $NC(G)$ of $G$ is the simplicial complex on $V$ whose faces are noncovers of $G$. The independence domination number $i\gamma (G)$ of $G$ is the minimum integer $k$ such that every independent set of $G$ can be dominated by $k$ vertices. In this note, we prove that $NC(G)$ is $(|V|-i\gamma (G)-1)$-collapsible.