Independence complexes of stable Kneser graphs

zbMATH Open1217.05174arXiv0912.0720MaRDI QIDQ540129FDOQ540129

Benjamin Braun

Publication date: 1 June 2011

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: For integers ngeq 1, kgeq 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}.

Full work available at URL: https://arxiv.org/abs/0912.0720

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

homotopy typesindependence complexes

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Relations of low-dimensional topology with graph theory (57M15)

Cited In (14)

• Deformation retracts of neighborhood complexes of stable Kneser graphs
• Complexes of graphs with bounded independence number
• Distance \(r\)-domination number and \(r\)-independence complexes of graphs
• Homotopy type of neighborhood complexes of Kneser graphs, \(KG_{2,k}\)
• Matching and independence complexes related to small grids
• The neighborhood complexes of almost \(s\)-stable Kneser graphs
• Title not available (Why is that?)
• Clique complexes and graph powers
• A generalization of an independent set with application to \((K_q; k)\)-stable graphs
• Star clusters in independence complexes of graphs
• On 4-chromatic Schrijver graphs: their structure, non-3-colorability, and critical edges
• Matching complexes of trees and applications of the matching tree algorithm
• Neighborhood complexes of stable Kneser graphs
• On the diameter of Schrijver graphs

This page was built for publication: Independence complexes of stable Kneser graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q540129)