Topological obstructions to graph colorings

DOI10.1090/S1079-6762-03-00112-4MaRDI QIDQ4680992zbMATHOpenAlexFDO

Authors Dmitry N. Kozlov, Eric Babson

Publication date 14 June 2005

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

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

zbMATH Keywords

cell complexconjecture of Lovász

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

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.

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

Cites work

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

Cited in

(22)

• Complexes of graph homomorphisms
• A simple proof for folds on both sides in complexes of graph homomorphisms
• Set partition complexes
• 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
• A topological lower bound for the chromatic number of a special family of graphs
• scientific article; zbMATH DE number 816131 (Why is no real title available?)
• Homology tests for graph colorings
• Local chromatic number and distinguishing the strength of topological obstructions
• Topologically 4-chromatic graphs and signatures of odd cycles
• Obstructions to locally injective oriented improper colourings
• Cobounding odd cycle colorings
• Graph colorings, spaces of edges and spaces of circuits
• The neighborhood complex of a random graph
• A short proof of a conjecture on the connectivity of graph coloring complexes
• Generalized Borsuk graphs
• scientific article; zbMATH DE number 2211584 (Why is no real title available?)
• Simple homotopy types of Hom-complexes, neighborhood complexes, Lovász complexes, and atom crosscut complexes
• Proof of the Lovász conjecture
• Combinatorial groupoids, cubical complexes, and the Lovász Conjecture
• WI-posets, graph complexes and \(\mathbb{Z}_2\)-equivalences
• Collapsing along monotone poset maps
• Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes

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)