Abstract
In [14] Matoušek and Ziegler compared various topological lower bounds for the chromatic number. They proved that Lovász’s original bound [9] can be restated as X(G) ≥ ind(B(G)) + 2. Sarkaria’s bound [15] can be formulated as X(G) ≥ ind(B0(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. The most interesting result is that up to ℤ2-homotopy the box complex B(G) can be any ℤ2-space. This together with topological constructions allows us to construct graphs showing that the mentioned two bounds are different. Some of the results were announced in [14].
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
E. Babson and D. N. Kozlov: Complexes of graph homomorphisms, Israel J. Math.152 (2006), 285–312.
A. Björner: Topological methods, in Handbook of Combinatorics (R. Graham, M. Grötschel and L. Lovász, eds.), Vol. II, Chapter 34, pp. 1819–1872, North-Holland, Amsterdam, 1995.
A. Björner and M. de Longueville: Neighborhood complexes of stable Kneser graphs, Combinatorica23(1) (2003), 23–34.
G. E. Bredon: Equivariant Cohomology Theories, Lecture Notes in Mathematics, 34, Springer-Verlag, Berlin etc., 1967.
P. E. Conner and E. E. Floyd: Fixed point free involutions and equivariant maps, Bull. Amer. Math. Soc.66 (1960), 416–441.
A. Hatcher: Algebraic Topology, Cambridge University Press, 2001/02, electronic version: http://www.math.cornell.edu/~hatcher/AT/ATpage.html
P. J. Hilton and S. Wylie: Homology Theory: An Introduction to Algebraic Topology, Cambridge University Press, 1960.
M. Kneser: Aufgabe 360, Jahresbericht der DMV58(2) (1955), pp. 2. Abteilung, S. 27.
L. Lovász: Kneser’s conjecture, chromatic number and homotopy; J. Combinatorial Theory, Ser. A25 (1978), 319–324.
A. T. Lundell and S. Weingram: Topology of CW Complexes, Van Nostrand, New York, 1969.
K. V. Madahar: Simplicial maps from the 3-sphere to the 2-sphere, Adv. Geom.2(2) (2002), 99–106.
K. V. Madahar and K. S. Sarkaria: A minimal triangulation of the Hopf map and its application, Geom. Dedicata82(1–3) (2000), 105–114.
J. Matoušek: Using the Borsuk-Ulam Theorem; Lectures on Topological Methods in Combinatorics and Geometry, Universitext, Springer-Verlag, Heidelberg, 2003.
J. Matoušek and G. M. Ziegler: Topological lower bounds for the chromatic number: A hierarchy; Jahresbericht der DMV106 (2004), 71–90.
K. S. Sarkaria: A generalized Kneser conjecture, J. Comb. Theory, Ser. B49 (1990), 236–240.
J. W. Walker: From graphs to ortholattices and equivariant maps, J. Comb. Theory, Ser. B35 (1983), 171–192.
R. T. Živaljević: WI-posets, graph complexes and ℤ2-equivalences, J. Comb. Theory, Ser. A111(2) (2005), 204–223.
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by the joint Berlin/Zürich graduate program Combinatorics, Geometry, and Computation, financed by ETH Zürich and the German Science Foundation (DFG).