##
Einar Steingrimsson: the Coloring Complex of a Graph
and the Chromatic Polynomia

###
Abstract

Let G be a graph with vertex set [n] = {1,2,...,n}. The coloring complex of G is a simplicial complex whose
Stanley-Reisner ring is the quotient of a certain (nice) ring by the coloring ideal of G, an ideal whose monomials
are in one-to-one correspondence with the proper colorings of G. Knowing the Hilbert series of this ideal (or the
quotient ring) is therefore equivalent to knowing the chromatic polynomial of G.
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.

###