Linear colorings of simplicial complexes and collapsing |
| |
Authors: | Yusuf Civan |
| |
Institution: | a Department of Mathematics, Suleyman Demirel University, Isparta 32260, Turkey b Department of Mathematics, Bilkent University, Ankara 06800, Turkey |
| |
Abstract: | A vertex coloring of a simplicial complex Δ is called a linear coloring if it satisfies the property that for every pair of facets (F1,F2) of Δ, there exists no pair of vertices (v1,v2) with the same color such that v1∈F1?F2 and v2∈F2?F1. The linear chromatic numberlchr(Δ) of Δ is defined as the minimum integer k such that Δ has a linear coloring with k colors. We show that if Δ is a simplicial complex with lchr(Δ)=k, then it has a subcomplex Δ′ with k vertices such that Δ is simple homotopy equivalent to Δ′. As a corollary, we obtain that lchr(Δ)?Homdim(Δ)+2. We also show in the case of linearly colored simplicial complexes, the usual assignment of a simplicial complex to a multicomplex has an inverse. Finally, we show that the chromatic number of a simple graph is bounded from above by the linear chromatic number of its neighborhood complex. |
| |
Keywords: | Simplicial complex Poset homotopy Multicomplex Collapsing Nonevasiveness Graph coloring Chromatic number |
本文献已被 ScienceDirect 等数据库收录! |
|