The coloring ideal and coloring complex of a graph

Steingrímsson, Einar

Journal of Algebraic Combinatorics, Tome 14 (2001) no. 1, pp. 73-84.

Résumé

Summary: 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 Stanley-Reisner ring of a simplicial complex $C$. The $h$-vector of $C$ is a certain transformation of the $tail T( n) = n ^{d} - chi( n)$ of the chromatic polynomial $chi$ 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$.

Détail

Keywords: chromatic polynomial, monomial ideal, simplicial complex, Stanley-Reisner ring, Hilbert polynomial, Euler characteristic, acyclic orientations