Graph colorings, spaces of edges and spaces of circuits
From MaRDI portal
(Redirected from Publication:1028347)
Abstract: By Lovasz' proof of the Kneser conjecture, the chromatic number of a graph G is bounded from below by the index of the Z_2-space Hom(K_2,G) plus two. We show that the cohomological index of Hom(K_2,G) is also greater than the cohomological index of the Z_2-space Hom(C_{2r+1}, G) for r>0. This gives a new and simple proof of the strong form of the graph colouring theorem by Babson and Kozlov, which had been conjectured by Lovasz, and at the same time shows that it never gives a stronger bound than can be obtained by Hom(K_2, G). The proof extends ideas introduced by Zivaljevic in a previous elegant proof of a special case. We then generalise the arguments and obtain conditions under which corresponding results hold for other graphs in place of C_{2r+1}. This enables us to find an infinite family of test graphs of chromatic number 4 among the Kneser graphs. Our main new result is a description of the Z_2-homotopy type of the direct limit of the system of all the spaces Hom(C_{2r+1}, G) in terms of the Z_2-homotopy type of Hom(K_2, G). A corollary is that the coindex of Hom(K_2, G) does not exceed the coindex of Hom(C_{2r+1}, G) by more then one if r is chosen sufficiently large. Thus the graph colouring bound in the theorem by Babson & Kozlov is also never weaker than that from Lovasz' proof of the Kneser conjecture.
Recommendations
- Topological lower bounds for the chromatic number: a hierarchy
- Proof of the Lovász conjecture
- A short proof of \(w_{1}^n (\text{Hom}(C_{2r+1}, K_{n+2})) = 0\) for all \(n\) and a graph colouring theorem by Babson and Kozlov
- Complexes of graph homomorphisms
- Topological obstructions to graph colorings
Cites work
- A counterexample to a conjecture of Björner and Lovász on the \(\chi\)-coloring complex
- Canonical homeomorphisms of posets
- Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes
- Cohomology of colorings of cycles
- Combinatorial groupoids, cubical complexes, and the Lovász Conjecture
- Complexes of graph homomorphisms
- Graph coloring manifolds
- scientific article; zbMATH DE number 2103273 (Why is no real title available?)
- scientific article; zbMATH DE number 3390006 (Why is no real title available?)
- Kneser's conjecture, chromatic number, and homotopy
- On the Kunneth Formula and Functorial Dependence in Algebraic Topology
- Proof of the Lovász conjecture
- Small models of graph colouring manifolds and the Stiefel manifolds \(\Hom(C_{5},K_n)\)
- The homotopy type of complexes of graph homomorphisms between cycles
- Topology of Hom complexes and test graphs for bounding chromatic number
- Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler
Cited in
(21)- Homotopy groups of Hom complexes of graphs
- A topological lower bound for the chromatic number of a special family of graphs
- Topology of Hom complexes and test graphs for bounding chromatic number
- Homomorphism complexes and maximal chains in graded posets
- \(\mathbb{Z}_2\)-indices and Hedetniemi's conjecture
- Knight move in chromatic cohomology
- Homomorphism complexes, reconfiguration, and homotopy for directed graphs
- scientific article; zbMATH DE number 3855142 (Why is no real title available?)
- Cohomology of colorings of cycles
- Stiefel manifolds and coloring the pentagon
- On pallets for Fox colorings of spatial graphs
- Answers to some problems about graph coloring test graphs
- Paths of homomorphisms from stable Kneser graphs
- Hedetniemi's conjecture and strongly multiplicative graphs
- Hom complexes and homotopy in the category of graphs
- Deformation retracts of neighborhood complexes of stable Kneser graphs
- The equivariant topology of stable Kneser graphs
- Hom complexes of graphs whose codomains are square-free
- Box complexes: at the crossroad of graph theory and topology
- Set partition complexes
- On the topological lower bound for the multichromatic number
This page was built for publication: Graph colorings, spaces of edges and spaces of circuits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1028347)
