Bounded degree complexes of forests

Abstract

Given an arbitrary sequence of non-negative integers $\vec{\lambda }=({\lambda }_1,\dots ,{\lambda }_n)$ and a graph $G$ with vertex set $\{v_1,\dots ,v_n\}$, the bounded degree complex, denoted ${\text{BD}}^{\vec{\lambda }}(G)$, is a simplicial complex whose faces are the subsets $H\subseteq E(G)$ such that for each $i\in \{1,\dots ,n\}$, the degree of vertex $v_i$ in the induced subgraph $G[H]$ is at most ${\lambda }_i$. When ${\lambda }_i=k$ for all $i$, the bounded degree complex ${\text{BD}}^{\vec{\lambda }}(G)$ is called the $k$-matching complex, denoted $M_k(G)$. In this article, we determine the homotopy type of bounded degree complexes of forests. In particular, we show that, for all $k\ge 1$, the $k$-matching complexes of caterpillar graphs are either contractible or homotopy equivalent to a wedge of spheres, thereby proving a conjecture of Julianne Vega \cite[Conjecture 7.3]{Vega19}. We also give a closed form formula for the homotopy type of the bounded degree complexes of those caterpillar graphs in which every non-leaf vertex is adjacent to at least one leaf vertex.

13 pages

Cited by in corpus (3)

• Independence complexes of hypergraphs and bounded degree complexes
• Vertex decomposability of complexes associated to forests
• The graph minor theorem in topological combinatorics