Topological obstructions to graph colorings

DOI10.1090/S1079-6762-03-00112-4zbMATH Open1063.05041arXivmath/0305300OpenAlexW1485574018MaRDI QIDQ4680992FDOQ4680992

Eric Babson, Dmitry N. Kozlov

Publication date: 14 June 2005

Published in: Electronic Research Announcements of the American Mathematical Society (Search for Journal in Brave)

Abstract: For any two graphs $G$ and $H$ Lov'asz has defined a cell complex $Hom(G,H)$ having in mind the general program that the algebraic invariants of these complexes should provide obstructions to graph colorings. Here we announce the proof of a conjecture of Lov'asz concerning these complexes with $G$ a cycle of odd length. More specifically, we show that: if $Hom(C_{2r+1},G)$ is $k$-connected, then $chi(G)geqk+4$. Our actual statement is somewhat sharper, as we find obstructions already in the non-vanishing of powers of certain Stiefel-Whitney classes.

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

Recommendations

• Proof of the Lovász conjecture
• Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes
• A short proof of a conjecture on the connectivity of graph coloring complexes
• Complexes of graph homomorphisms
• Homology tests for graph colorings

zbMATH Keywords

cell complexconjecture of Lovász

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Higher algebraic K-theory: I
• Kneser's conjecture, chromatic number, and homotopy
• Generalized Kneser coloring theorems with combinatorial proofs

Cited In (12)

• A simple proof for folds on both sides in complexes of graph homomorphisms
• 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
• Title not available (Why is that?)
• Simple homotopy types of Hom-complexes, neighborhood complexes, Lovász complexes, and atom crosscut complexes
• WI-posets, graph complexes and \(\mathbb{Z}_2\)-equivalences
• Title not available (Why is that?)
• Collapsing along monotone poset maps
• Generalized Borsuk graphs
• Cobounding odd cycle colorings
• Complexes of graph homomorphisms
• Obstructions to locally injective oriented improper colourings
• The neighborhood complex of a random graph

This page was built for publication: Topological obstructions to graph colorings

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