On the diameter of Schrijver graphs

PASTINE, ADRIÁN; TORRES, PABLO; VALENCIA-PABON, MARIO

Procedia Computer Science

Elsevier

Año: 2021

1877-0509

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 that the diameter of $operatorname{SG}(2k+r,k)$ is equal to $2$ if $r geq 2k-2$; $3$ if $k-2 leq r leq 2k-3$; $k$ if $r=1$; and for $2 leq r leq k-3$, we obtain that the diameter of $operatorname{SG}(2k+r,k)$ is at most equal to $k-r+1$.