Independence Complexes of Stable Kneser Graphs

Details Independence Complexes of Stable Kneser Graphs Independence Complexes of Stable Kneser Graphs

2009-12-03

arxiv.org/abs/0912.0720v1

Mathematics

Combinatorics

submitted

Scientific paper

For integers n\geq 1, k\geq 0, the stable Kneser graph SG_{n,k} (also called the Schrijver graph) has as vertex set the stable n-subsets of [2n+k] and as edges disjoint pairs of n-subsets, where a stable n-subset is one that does not contain any 2-subset of the form {i,i+1} or {1,2n+k}. The stable Kneser graphs have been an interesting object of study since the late 1970's when A. Schrijver determined that they are a vertex critical class of graphs with chromatic number k+2. This article contains a study of the independence complexes of SG_{n,k} for small values of n and k. Our contributions are two-fold: first, we find that the homotopy type of the independence complex of SG_{2,k} is a wedge of spheres of dimension two. Second, we determine the homotopy types of the independence complexes of certain graphs related to SG_{n,2}.

Affiliated with

Also associated with

No associations

Rating

Independence Complexes of Stable Kneser Graphs 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 Independence Complexes of Stable Kneser Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Independence Complexes of Stable Kneser Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-518023