On the diameter of Schrijver graphs

Abstract

For k ≥ 1 and n ≥ 2k, the well known Kneser graph KG(n, k) has all k-element subsets of an n-element set as vertices; two such subsets are adjacent if they are disjoint. Schrijver constructed a vertex-critical subgraph SG(n, k) of KG(n, k) with the same chromatic number. In this paper, we compute the diameter of the graph SG(2k + r, k) with r ≥ 1. We obtain an exact value of the diameter of SG(2k + r, k) when r ∈ {1, 2} or when r ≥ k − 3. For the remaining cases, when 3 ≤ r ≤ k − 4, we show that the diameter of SG(2k + r, k) belongs to the set {4, . . . , k − r − 1}.