Topological lower bounds for the chromatic number: A hierarchy

Details Topological lower bounds for the chromatic number: A hierarchy Topological lower bounds for the chromatic number: A hierarchy

2002-08-09

arxiv.org/abs/math/0208072v3

Mathematics

Combinatorics

16 pages, 1 figure. Jahresbericht der DMV, to appear

Scientific paper

This paper is a study of ``topological'' lower bounds for the chromatic number of a graph. Such a lower bound was first introduced by Lov\'asz in 1978, in his famous proof of the \emph{Kneser conjecture} via Algebraic Topology. This conjecture stated that the \emph{Kneser graph} $\KG_{m,n}$, the graph with all $k$-element subsets of $\{1,2,...,n\}$ as vertices and all pairs of disjoint sets as edges, has chromatic number $n-2k+2$. Several other proofs have since been published (by B\'ar\'any, Schrijver, Dolnikov, Sarkaria, Kriz, Greene, and others), all of them based on some version of the Borsuk--Ulam theorem, but otherwise quite different. Each can be extended to yield some lower bound on the chromatic number of an arbitrary graph. (Indeed, we observe that \emph{every} finite graph may be represented as a generalized Kneser graph, to which the above bounds apply.) We show that these bounds are almost linearly ordered by strength, the strongest one being essentially Lov\'asz' original bound in terms of a neighborhood complex. We also present and compare various definitions of a \emph{box complex} of a graph (developing ideas of Alon, Frankl, and Lov\'asz and of \kriz). A suitable box complex is equivalent to Lov\'asz' complex, but the construction is simpler and functorial, mapping graphs with homomorphisms to $\Z_2$-spaces with $\Z_2$-maps.

Affiliated with

Also associated with

No associations

Rating

Topological lower bounds for the chromatic number: A hierarchy does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Topological lower bounds for the chromatic number: A hierarchy, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Topological lower bounds for the chromatic number: A hierarchy will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-666460