On the diameter of Schrijver graphs

AGUSTINA VICTORIA LEDEZMA; ADRIÁN PASTINE; PABLO TORRES; MARIO VALENCIA-PABON

DISCRETE APPLIED MATHEMATICS

ELSEVIER SCIENCE BV

Lugar: Amsterdam; Año: 2024 vol. 350 p. 15 - 30

0166-218X

For $k geq 1$ and $n geq 2k$, the well known Kneser graph $operatorname{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 $operatorname{SG}(n,k)$ of $operatorname{KG}(n,k)$ with the same chromatic number. In this paper, we compute the diameter of the graph $operatorname{SG}(2k+r,k)$ with $r geq 1$. We obtain an exact value of the diameter of $operatorname{SG}(2k+r,k)$ when $r in {1,2}$ or when $r geq k-3$. For the remaining cases, when $3 leq r leq k-4$, we show that the diameter of $operatorname{SG}(2k+r,k)$ belongs to the set ${4,ldots,k-r-1}$.