On the neighborhood complex of s→-stable Kneser graphs

Hamid Reza Daneshpajouh, József Osztényi

Research output: Journal PublicationArticlepeer-review

1 Citation (Scopus)

Abstract

In 2002, Björner and de Longueville showed the neighborhood complex of the 2-stable Kneser graph KG(n,k)2−stab has the same homotopy type as the (n−2k)-sphere. A short time ago, an analogous result about the homotopy type of the neighborhood complex of almost s-stable Kneser graph has been announced by the second author. Combining this result with the famous Lovász's topological lower bound on the chromatic number of graphs yielded a new way for determining the chromatic number of these graphs which was determined a bit earlier by Chen. In this paper we present a common generalization of the mentioned results. For given an integer vector s→=(s1,…,sk), first we define s→-stable Kneser graph KG(n,k)s→−stab as an induced subgraph of the Kneser graph KG(n,k). Then, we show that the neighborhood complex of KG(n,k)s→−stab has the same homotopy type as the n−∑i=1k−1si−2-sphere for some specific values of the parameter s→. In particular, this implies that χKG(n,k)s→−stab=n−∑i=1k−1si for those parameters. Moreover, as a simple corollary of this result, we give a lower bound on the chromatic number of 3-stable Kneser graphs which is just one less than the number conjectured in this regard.

Original languageEnglish
Article number112302
JournalDiscrete Mathematics
Volume344
Issue number4
DOIs
Publication statusPublished - Apr 2021
Externally publishedYes

Keywords

  • Chromatic number
  • Hom-complex
  • Neighborhood complex
  • Stable Kneser graphs

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'On the neighborhood complex of s→-stable Kneser graphs'. Together they form a unique fingerprint.

Cite this