The topology of the coloring complex

Jonsson, Jakob

Journal of Algebraic Combinatorics, Tome 21 (2005) no. 3, pp. 311-329.

Résumé

Summary: In a recent paper, E. Steingrímsson associated to each simple graph $G$ a simplicial complex $Delta_{ G}$, referred to as the coloring complex of $G$. Certain nonfaces of $Delta_{ G}$ correspond in a natural manner to proper colorings of $G$. Indeed, the $h$-vector is an affine transformation of the chromatic polynomial $chi_{ G}$ of $G$, and the reduced Euler characteristic is, up to sign, equal to | $chi_{ G}$(-1)|-1. We show that $Delta_{ G}$ is constructible and hence Cohen-Macaulay. Moreover, we introduce two subcomplexes of the coloring complex, referred to as $polar$ coloring complexes. The $h$-vectors of these complexes are again affine transformations of $chi_{ G}$, and their Euler characteristics coincide with $chiprime_{ G}(0)$ and - $chiprime_{ G}(1)$, respectively. We show for a large class of graphs-including all connected graphs-that polar coloring complexes are constructible. Finally, the coloring complex and its polar subcomplexes being Cohen-Macaulay allows for topological interpretations of certain positivity results about the chromatic polynomial due to N. Linial and I. M. Gessel.

Détail

Keywords: key words topological combinatorics, constructible complex, Cohen-Macaulay complex, chromatic polynomial