|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Topological lower bounds for the chromatic number: A hierarchy | | Jiri Matousek
; Günter M. Ziegler
; | | Date: |
9 Aug 2002 | | Subject: | Combinatorics; Algebraic Topology MSC-class: 05C15; 05A05; 55M35 | math.CO math.AT | | Abstract: | 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ász 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árány, 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ász’ 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ász and of kriz). A suitable box complex is equivalent to Lovász’ complex, but the construction is simpler and functorial, mapping graphs with homomorphisms to $_2$-spaces with $_2$-maps. | | Source: | arXiv, math.CO/0208072 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER