Higher connectivity of graph coloring complexes

Details Higher connectivity of graph coloring complexes Higher connectivity of graph coloring complexes

2004-10-14

arxiv.org/abs/math/0410335v2

IMRN 2005:25 (2005) 1543-1562.

Mathematics

Combinatorics

16 pages, 6 figures

Scientific paper

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\'asz 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\geq 3$.

Affiliated with

Also associated with

No associations

Rating

Higher connectivity of graph coloring complexes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Higher connectivity of graph coloring complexes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Higher connectivity of graph coloring complexes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-664844