首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 v1F1?F2 and v2F2?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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号