TY - JOUR

T1 - Independence complexes of stable kneser graphs

AU - Braun, Benjamin

PY - 2011

Y1 - 2011

N2 - For integers n ≥ 1, k ≥ 0, the stable Kneser graph SGn,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 SGn,k for small values of n and k. Our contributions are two-fold: first, we prove that the homotopy type of the independence complex of SG2,k is a wedge of spheres of dimension two. Second, we determine the homotopy types of the independence complexes of certain graphs related to SGn,2.

AB - For integers n ≥ 1, k ≥ 0, the stable Kneser graph SGn,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 SGn,k for small values of n and k. Our contributions are two-fold: first, we prove that the homotopy type of the independence complex of SG2,k is a wedge of spheres of dimension two. Second, we determine the homotopy types of the independence complexes of certain graphs related to SGn,2.

UR - http://www.scopus.com/inward/record.url?scp=79959287311&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79959287311&partnerID=8YFLogxK

U2 - 10.37236/605

DO - 10.37236/605

M3 - Article

AN - SCOPUS:79959287311

SN - 1077-8926

VL - 18

SP - 1

EP - 17

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 1

ER -