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-ZMaRDI QIDQ839909zbMATH OpenOpenAlexFDO

Authors Carsten A. Schultz

Publication date 3 September 2009

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

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)

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.

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

Cites work

• Canonical homeomorphisms of posets
• Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes
• Cobounding odd cycle colorings
• Complexes of graph homomorphisms
• Graph coloring manifolds
• Kneser's conjecture, chromatic number, and homotopy
• Proof of the Lovász conjecture
• Small models of graph colouring manifolds and the Stiefel manifolds \(\Hom(C_{5},K_n)\)
• Topological obstructions to graph colorings

Cited in

(8)

• Set partition complexes
• Stiefel manifolds and coloring the pentagon
• \(\mathbb{Z}_2\)-indices and Hedetniemi's conjecture
• Cobounding odd cycle colorings
• Graph colorings, spaces of edges and spaces of circuits
• Topology of Hom complexes and test graphs for bounding chromatic number
• Answers to some problems about graph coloring test graphs
• Proof of the Lovász conjecture

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)