Independence complexes of stable kneser graphs

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)1-17
Number of pages17
JournalElectronic Journal of Combinatorics
Volume18
Issue number1
DOIs
StatePublished - 2011

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Independence complexes of stable kneser graphs'. Together they form a unique fingerprint.

Cite this