## 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→=(s_{1},…,s_{k}), 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=1}^{k−1}s_{i}−2-sphere for some specific values of the parameter s→. In particular, this implies that χKG(n,k)_{s→−stab}=n−∑_{i=1}^{k−1}s_{i} 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 language | English |
---|---|

Article number | 112302 |

Journal | Discrete Mathematics |

Volume | 344 |

Issue number | 4 |

DOIs | |

Publication status | Published - Apr 2021 |

Externally published | Yes |

## Keywords

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

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics