| Abstract: | In a recent paper, E. Steingrímsson associated to each simple graph G a simplicial complex  G, referred to as the coloring complex of G. Certain nonfaces of G correspond in a natural manner to proper colorings of G. Indeed, the h-vector is an affine transformation of the chromatic polynomial  G of G, and the reduced Euler characteristic is, up to sign, equal to |G(–1)|–1. We show that G is constructible and hence Cohen-Macaulay. Moreover, we introduce two subcomplexes of the coloring complex, referred to as polar coloring complexes. The h-vectors of these complexes are again affine transformations of G, and their Euler characteristics coincide with  G(0) and –G(1), respectively. We show for a large class of graphs—including all connected graphs—that polar coloring complexes are constructible. Finally, the coloring complex and its polar subcomplexes being Cohen-Macaulay allows for topological interpretations of certain positivity results about the chromatic polynomial due to N. Linial and I. M. Gessel.Research financed by EC s IHRP Programme, within the Research Training Network  Algebraic Combinatorics in Europe, grant HPRN-CT-2001-00272. |
