Linear colorings of simplicial complexes and collapsing


Civan Y. , YALCIN E.

JOURNAL OF COMBINATORIAL THEORY SERIES A, cilt.114, sa.7, ss.1315-1331, 2007 (SCI İndekslerine Giren Dergi) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 114 Konu: 7
  • Basım Tarihi: 2007
  • Doi Numarası: 10.1016/j.jcta.2007.02.001
  • Dergi Adı: JOURNAL OF COMBINATORIAL THEORY SERIES A
  • Sayfa Sayıları: ss.1315-1331

Özet

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.