The faces of the coloring complex can be identified with ordered partitions of the set [n] where some block contains the vertices of an edge of G. An ordered partition of a set is a partition whose blocks have been ordered linearly (arbitrarily permuted). The coloring complex is closely related to the so called graphic hyperplane arrangement for G, and it has been shown (by Hultman) to be shellable.
The Kruskal-Katona conditions on f-vectors of simplicial complexes, applied to a complex derived from the coloring complex, give new restrictions a polynomial must satisfy in order to be chromatic. With minor exceptions, it seems that two non-isomorphic graphs have non-isomorphic coloring complexes. The hope is therefore that the coloring complex can be used to deduce more results about graphs, or classes of graphs, in particular about which polynomials are chromatic.
I will report on older work of myself and others, as well as on joint work in progress with Martina Kubitzke and Helene Barcelo.