The Topology of Intersections of Coloring Complexes

In a construction due to Steingrmsson, a simplicial complex is asso-ciated to each simple graph; the complex is the coloring complex of the graph. Some of the nonfaces of the coloring complex correspond in a nat-ural manner to proper colorings of the graph. Indeed, the h-vector of the complex is a certain ane transformation of the chromatic polynomial. In an earlier paper we showed that the coloring complex is constructible and hence Cohen-Macaulay. In this paper, we consider some other variants of the coloring complex corresponding to colorings that are proper for a certain number of graphs in a given sequence of graphs. Again, these com-plexes have attractive topological properties as soon as certain technical conditions are satised.