Higher connectivity of graph coloring complexes

2004/10/31 by Sonja Lj. Cukic, Dmitry N. Kozlov
Mathematics · #math.CO #math.AT #msc:05C15 #msc:57M15

paper · pdf

published as IMRN 2005:25 (2005) 1543-1562. · 16 pages, 6 figures

arxiv created 2005/01/31 · arxiv updated 2009/12/01

Abstract

The main result of this paper is a proof of the following conjecture of Babson & Kozlov: Theorem. Let G be a graph of maximal valency d, then the complex Hom(G,K_n) is at least (n-d-2)-connected. Here Hom(-,-) denotes the polyhedral complex introduced by Lovász to study the topological lower bounds for chromatic numbers of graphs. We will also prove, as a corollary to the main theorem, that the complex Hom(C_2r+1,K_n) is (n-4)-connected, for n≥ 3.

Related

• A short proof of a conjecture on the higher connectivity of graph coloring complexes
• Connectedness of Certain Graph Coloring Complexes
• Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes
• Homomorphism Complexes and k-Cores
• Lovász' original lower bound: Getting tighter bounds and Reducing computational complexity