The Forest Filtration of a Graph

Abstract

Given a graph $G$, we define a filtration of simplicial complexes associated to $G$, ${\mathcal{F}}_0(G)\subseteq {\mathcal{F}}_1(G)\subseteq \cdots \subseteq {\mathcal{F}}_{\infty }(G)$ where the first complex is the independence complex and the last the complex is formed by the acyclic sets of vertices. We prove some properties of this filtration and we calculate the homotopy type for various families of graphs. We give an upper bound for the decycling number and generalizations of this parameter using the dimensions of the rational cohomology groups of these complexes. We also derive an upper bound for the Fibonacci numbers of ternary graphs.