%0 Journal Article
%T Linear colorings of simplicial complexes and collapsing
%A Yusuf Civan
%A Ergun Yalcin
%J Mathematics
%D 2006
%I arXiv
%X 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'$ with $k$ vertices such that $\Delta'$ is a strong deformation retract of $\Delta$. We also prove that this deformation is a nonevasive reduction, in particular, a collapsing.
%U http://arxiv.org/abs/math/0604628v1