Change search
ReferencesLink to record
Permanent link

Direct link
The topology of the coloring complex
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
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
Abstract [en]

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 |χ(G)(-1)| -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.
Keyword [en]
topological combinatorics, constructible complex, Cohen-Macaulay complex, chromatic polynomial, acyclic orientations, rings, posets, graphs
URN: urn:nbn:se:kth:diva-14750DOI: 10.1007/s10801-005-6914-0ISI: 000229092600005ScopusID: 2-s2.0-18744406024OAI: diva2:332791
QC 20100525Available from: 2010-08-05 Created: 2010-08-05Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Jonsson, Jakob
By organisation
Mathematics (Div.)
In the same journal
Journal of Algebraic Combinatorics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 33 hits
ReferencesLink to record
Permanent link

Direct link