Let G be a simple graph on d vertices. We define a monomial ideal K in the Stanley-Reisner ring A of the order complex of the Boolean algebra on d atoms. The monomials in K are in one-to-one correspondence with the proper colorings of G. In particular, the Hilbert polynomial of K equals the chromatic polynomial of G. The ideal K is generated by square-free monomials, so A/K is the StanleyReisner ring of a simplicial complex C. The h-vector of C is a certain transformation of the tail T (n) = n d − χ (n) of the chromatic polynomial χ of G. The combinatorial structure of the complex C is described explicitly and it is shown that the Euler characteristic of C equals the number of acyclic orientations of G.
Steingrímsson REF showed that for any graph G the chromatic polynomial χ G (k + 1) shifted by one is the Hilbert function of a module with a particular structure.
The coloring ideal and coloring complex of a graph
J. Algebraic Combin
Mathematics