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.
@article{10_37236_8684,
author = {Ilkyoo Choi and Jinha Kim and Boram Park},
title = {Collapsibility of non-cover complexes of graphs},
journal = {The electronic journal of combinatorics},
year = {2020},
volume = {27},
number = {1},
doi = {10.37236/8684},
zbl = {1431.05111},
url = {http://geodesic.mathdoc.fr/articles/10.37236/8684/}
}
TY - JOUR
AU - Ilkyoo Choi
AU - Jinha Kim
AU - Boram Park
TI - Collapsibility of non-cover complexes of graphs
JO - The electronic journal of combinatorics
PY - 2020
VL - 27
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/8684/
DO - 10.37236/8684
ID - 10_37236_8684
ER -
%0 Journal Article
%A Ilkyoo Choi
%A Jinha Kim
%A Boram Park
%T Collapsibility of non-cover complexes of graphs
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/8684/
%R 10.37236/8684
%F 10_37236_8684
Ilkyoo Choi; Jinha Kim; Boram Park. Collapsibility of non-cover complexes of graphs. The electronic journal of combinatorics, Tome 27 (2020) no. 1. doi: 10.37236/8684
