Linear colorings of simplicial complexes and collapsing

Civan Y., YALCIN E.

JOURNAL OF COMBINATORIAL THEORY SERIES A, vol.114, no.7, pp.1315-1331, 2007 (Peer-Reviewed Journal) identifier identifier

  • Publication Type: Article / Article
  • Volume: 114 Issue: 7
  • Publication Date: 2007
  • Doi Number: 10.1016/j.jcta.2007.02.001
  • Journal Indexes: Science Citation Index Expanded, Scopus
  • Page Numbers: pp.1315-1331


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) is an element of F-1\F-2 and v(2) is an element of F-2\F-1. The linear chromatic number lchr(Delta) of Delta is defined as the minimum integer k such that Delta has a linear coloring with k colors. We show that if A is a simplicial complex with Ichr(Delta) = k, then it has a subcomplex Delta' with k vertices such that Delta is simple homotopy equivalent to Delta'. As a corollary, we obtain that lchr(Delta) >= Homdim(Delta) + 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 cht-ornatic number of its neighborhood complex. (C) 2007 Elsevier Inc. All rights reserved.