A short proof of w₁^n (Hom(C₂r+1, K_n+2)) = 0 for all n and a graph colouring theorem by Babson and Kozlov

DOI10.1007/S11856-009-0023-ZzbMATH Open1205.05096arXivmath/0507346OpenAlexW1990464011MaRDI QIDQ839909FDOQ839909

Carsten A. Schultz

Publication date: 3 September 2009

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

Abstract: We show that the n-th power of the first Stiefel-Whitney class of the Z_2-operation on the graph complex Hom(C_{2r+1},K_{n+2})$ is zero, confirming a conjecture by Babson and Kozlov. This proves the strong form of their graph colouring theorem, which they had only proven for odd n. Our proof is also considerably simpler than their proof of the weak form of the theorem, which is also known as the Lov'asz conjecture.

Full work available at URL: https://arxiv.org/abs/math/0507346

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Relations of low-dimensional topology with graph theory (57M15)

Cites Work

• Kneser's conjecture, chromatic number, and homotopy
• Complexes of graph homomorphisms
• Proof of the Lovász conjecture
• Title not available (Why is that?)
• Canonical homeomorphisms of posets
• Small models of graph colouring manifolds and the Stiefel manifolds \(\Hom(C_{5},K_n)\)
• Cobounding odd cycle colorings
• Title not available (Why is that?)
• Topological obstructions to graph colorings

Cited In (5)

• Set partition complexes
• Stiefel manifolds and coloring the pentagon
• \(\mathbb{Z}_2\)-indices and Hedetniemi's conjecture
• Answers to some problems about graph coloring test graphs
• Topology of Hom complexes and test graphs for bounding chromatic number

   Recommendations

• Proof of the Lovász conjecture 👍 👎
• A short proof of a conjecture on the connectivity of graph coloring complexes 👍 👎
• Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes 👍 👎
• Cobounding odd cycle colorings 👍 👎
• Topological obstructions to graph colorings 👍 👎

This page was built for publication: 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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q839909)