Collapsibility of non-cover complexes of graphs

Abstract

Let G be a graph on the vertex set V. A vertex subset W ⊆ V is a cover of G if V \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γ(G) −1)-collapsible where iγ(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.