Collapsibility of non-cover complexes of graphs (Q2290346)

Summary: 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\). G. Aharoni (personal communication) 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 [``Collapsibility of noncover complexes of chordal graphs'', Preprint, \url{arXiv:1904.04519}], who verified Aharoni's question in the affirmative for chordal graphs, we prove that the answer to the question is yes for all graphs.