Collapsibility of Non-Cover Complexes of Graphs

Abstract

Let $G$ be a graph on the vertex set $V$. A vertex subset $W \subseteq V$ is a cover of $G$ if $V \setminus W$ is an independent set of $G$, and $W$ is a non-cover of $G$ if $W$ is not a cover of $G$. The non-cover complex of $G$ is a simplicial complex on $V$ whose faces are non-covers of $G$. Then 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 independence 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.