Homology tests for graph colorings

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We describe a simple homological test for obstructions to graph colorings. The main idea is to combine the framework of Hom-complexes with the following general fact: an arbitrary Z_2-space has nontrivial homology with Z_2-coefficients in the dimension equal to its Stiefel-Whitney height. Actually, as a result we have a whole family of homology tests, one for each test graph. In general, these tests will give different answers, depending heavily on the choice of the test graph. We illustrate this phenomenon with some examples.
To appear in "Contemporary Mathematics"

Keywords

Algebraic Topology, Combinatorics, Primary: 55M35, Secondary 05C15, 57S17

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/115189

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0607750
 http://arxiv.org/abs/math/0607750

Collections

arXiv