Independence complexes of stable Kneser graphs

zbMATH Open1217.05174arXiv0912.0720MaRDI QIDQ540129FDOQ540129

Authors: 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.)

Recommendations

• The equivariant topology of stable Kneser graphs
• Neighborhood complexes of stable Kneser graphs
• Homotopy type of neighborhood complexes of Kneser graphs, \(KG_{2,k}\)
• On the neighborhood complex of \(\overrightarrow{s} \)-stable Kneser graphs
• The neighborhood complexes of almost \(s\)-stable Kneser graphs

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 (17)

• 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
• On the neighborhood complex of \(\overrightarrow{s} \)-stable Kneser graphs
• Star clusters in independence complexes of graphs
• Paths of homomorphisms from stable Kneser graphs
• The equivariant topology of stable Kneser 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)