Total Cut Complexes of Graphs

Abstract

Inspired by work of Fröberg (1990), and Eagon and Reiner (1998), we define the \emph{total $k$-cut complex} of a graph $G$ to be the simplicial complex whose facets are the complements of independent sets of size $k$ in $G$. We study the homotopy types and combinatorial properties of total cut complexes for various families of graphs, including chordal graphs, cycles, bipartite graphs, the prism $K_n\times K_2$, and grid graphs, using techniques from algebraic topology and discrete Morse theory.

25 pages, 2 figures, 3 tables. Minor revisions per referee comments. To appear in Discrete and Computational Geometry

Cited by in corpus (2)

• Topology of Cut Complexes of Graphs
• Topology of Cut Complexes II