The neighborhood complexes of almost s-stable Kneser graphs

摘要

In 1978, Laszlo Lovasz proved the famous Kneser Conjecture - concerning the chromatic number of the Kneser graphs KG(m,n) - introducing the neighborhood complex. In the same year, Alexander Schrijver defined certain induced subgraphs of KG(m,n) - called the stable Kneser graphs SG(m,n) - and showed that they are vertex-critical. Schrijver used another, Barany's method to obtain the chromatic number of the stable Kneser graphs. Almost 25 years later, in 2002, Anders Bjorner and Mark de Longueville studied the neighborhood complex of SG(m,n), and determined the homotopy type of them. Frederic Meunier generalized Schrijver's construction and formulated the conjecture on the chromatic number of the s-stable and almost s-stable Kneser graphs. We shall determine the homotopy type of the neighborhood complex of the almost s-stable Kneser graphs. In conjunction with Lovasz's topological bound on the chromatic number, we give the chromatic number of these graphs, which was recently determined by Chen using other methods. (C) 2018 Elsevier Ltd. All rights reserved.