The topology of the coloring complex
2005 (English)In: Journal of Algebraic Combinatorics, ISSN 0925-9899, E-ISSN 1572-9192, Vol. 21, no 3, 311-329 p.Article in journal (Refereed) Published
In a recent paper, E. Steingrimsson associated to each simple graph G a simplicial complex G., referred to as the coloring complex of G. Certain nonfaces of &UDelta;(G) correspond in a natural manner to proper colorings of G. Indeed, the h-vector is an affine transformation of the chromatic polynomial χ(G) of G, and the reduced Euler characteristic is, up to sign, equal to &VERBAR;χ(G)(-1)&VERBAR; -1. We show that &UDelta;(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 χ(G), and their Euler characteristics coincide with χ'(G)(0) and -χ'(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.
Place, publisher, year, edition, pages
2005. Vol. 21, no 3, 311-329 p.
topological combinatorics, constructible complex, Cohen-Macaulay complex, chromatic polynomial, acyclic orientations, rings, posets, graphs
IdentifiersURN: urn:nbn:se:kth:diva-14750DOI: 10.1007/s10801-005-6914-0ISI: 000229092600005ScopusID: 2-s2.0-18744406024OAI: oai:DiVA.org:kth-14750DiVA: diva2:332791
QC 201005252010-08-052010-08-05Bibliographically approved