Collapsibility of non-cover complexes of graphs

Abstract

Given a graph $G$, the non-cover complex of $G$ is the combinatorial Alexander dual of the independence complex of $G$. Aharoni asked if the non-cover complex of a graph $G$ without isolated vertices is $(|V(G)|-i\gamma (G)-1)$-collapsible where $i\gamma (G)$ denotes the independent domination number of $G$. Extending a result by the second author, who verified Aharoni's question in the affirmative for chordal graphs, we prove that the answer to the question is yes for all graphs. Namely, we show that for a graph $G$, the non-cover complex of a graph $G$ is $(|V(G)|-i\gamma (G)-1)$-collapsible.