Linear colorings of simplicial complexes and collapsing

Abstract

A vertex coloring of a simplicial complex $\Delta$ is called a linear coloring if it satisfies the property that for every pair of facets $(F_1,F_2)$ of $\Delta$, there exists no pair of vertices $(v_1,v_2)$ with the same color such that $v_1\in F_1\backslash F_2$ and $v_2\in F_2\backslash F_1$. We show that every simplicial complex $\Delta$ which is linearly colored with $k$ colors includes a subcomplex ${\Delta }^{\prime }$ with $k$ vertices such that ${\Delta }^{\prime }$ is a strong deformation retract of $\Delta$. We also prove that this deformation is a nonevasive reduction, in particular, a collapsing.

18 pages

References in corpus (1)

• Simple homotopy types of Hom-complexes, neighborhood complexes, Lovász complexes, and atom crosscut complexes