arXiv Analytics

Sign in

arXiv:math/0406118 [math.CO]AbstractReferencesReviewsResources

Homotopy types of box complexes

Peter Csorba

Published 2004-06-07Version 1

In [MZ04] Matousek and Ziegler compared various topological lower bounds for the chromatic number. They proved that Lovasz's original bound [L78] can be restated as $\chr G \geq \ind (\B(G)) +2$. Sarkaria's bound [S90] can be formulated as $\chr G \geq \ind (\B_0(G)) +1$. It is known that these lower bounds are close to each other, namely the difference between them is at most 1. In this paper we study these lower bounds, and the homotopy types of box complexes. Some of the results was announced in [MZ04].

Comments: 11 pages
Journal: Combinatorica, 27 (2007), no. 6, 669-682.
Categories: math.CO, math.AT
Subjects: 05C10, 05C15, 55P10
Related articles: Most relevant | Search more
arXiv:math/0310339 [math.CO] (Published 2003-10-21)
Box complexes, neighborhood complexes, and the chromatic number
arXiv:math/0208072 [math.CO] (Published 2002-08-09, updated 2003-11-24)
Topological lower bounds for the chromatic number: A hierarchy
arXiv:1212.3983 [math.CO] (Published 2012-12-17)
An Upper bound on the chromatic number of circle graphs without $K_4$

Links

Toolbox