Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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
Identifiers
URN: urn:nbn:se:kth:diva-14750DOI: 10.1007/s10801-005-6914-0ISI: 000229092600005Scopus ID: 2-s2.0-18744406024OAI: oai:DiVA.org:kth-14750DiVA: diva2:332791
Note
QC 20100525Available from: 2010-08-05 Created: 2010-08-05 Last updated: 2017-12-12Bibliographically 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

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 41 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf