Collapsibility of noncover complexes of chordal graphs
classification
🧮 math.CO
keywords
noncovercalledcomplexcovergammaindependentsubsetchordal
read the original abstract
Let $G$ be a graph on $V$. A vertex subset $S \subset V$ is called a cover of $G$ if its complement is an independent set, and $S$ is called a noncover if it is not a cover of $G$. A noncover complex $NC(G)$ of $G$ is the simplicial complex on $V$ whose faces are noncovers of $G$. The independence domination number $ i\gamma(G)$ of $G$ is the minimum integer $k$ such that every independent set of $G$ can be dominated by $k$ vertices. In this note, we prove that $NC(G)$ is $(|V|- i\gamma(G)-1)$-collapsible.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.