Let \([n]\)  denote the set \(\lbrace 1,\ldots ,n\rbrace \) . For positive integers \(n \ge 2k\) , the Kneser graph \(\operatorname{KG}(n,k)\)  has as vertices the \(k\) -subsets of \([n]\)  and two vertices are connected by an edge if they have empty intersection. In a famous paper, Lovász [1]} showed that its chromatic number \(\chi (\text{KG}(n,k))\)  is equal to \(n-2k+2\) . After this result, Schrijver [2]} proved that the chromatic number remains the same when we consider the subgraph \(\operatorname{KG}(n,k)_{2-\operatorname{stab}}\)  of \(\operatorname{KG}(n,k)\)  obtained by restricting the vertex set to the \(k\) -subsets that are 2-stable, that is, that do not contain two consecutive elements of \([n]\)  (where 1 and \(n\)  are considered also to be consecutive). Schrijver [2]} also proved that the 2-stable Kneser graphs are vertex critical (or \(\chi \) -critical), i.e. the chromatic number of any proper subgraph of \(\operatorname{KG}(n,k)_{2-\operatorname{stab}}\)  is strictly less than \(n-2k+2\) ; for this reason, the 2-stable Kneser graphs are also
known as the Schrijver graphs. From now on we will use throughout this paper the notation \(\operatorname{SG}(n,k)\)  to refer to the graph \(\operatorname{KG}(n,k)_{2-\operatorname{stab}}\) .
