2009/12/03 by Benjamin Braun, Braun, Benjamin · 2 citations
Computer Science · Mathematics · #05C69 #57M15 #Advanced Combinatorial Mathematics #Algebraic Topology (math.AT) #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Topological and Geometric Data Analysis #math.AT #math.CO #msc:05C69 #msc:57M15
paper · pdf · doi:10.48550/arxiv.0912.0720
submitted
arxiv created 2009/12/03 · openalex publication_date 2009/12/03 · arxiv updated 2009/12/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 find 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.