• 1 Institut für Mathematik

Schrijver introduced the stable Kneser graph $SG_{n,k}, n \geq 1, k \geq 0$. This graph is a vertex critical graph with chromatic number $k+2$, its vertices are certain subsets of a set of cardinality $m=2n+k$. Björner and de Longueville have shown that its box complex is homotopy equivalent to a sphere, $\mathrm{Hom}(K_2,SG_{n,k}) \simeq \mathbb{S}^k$. The dihedral group $D_{2m}$ acts canonically on $SG_{n,k}$. We study the $D_{2m}$ action on $\mathrm{Hom}(K_2,SG_{n,k})$ and define a corresponding orthogonal action on $\mathbb{R}^{k+1} \supset \mathbb{S}^k$. We establish a close equivariant relationship between the graphs $SG_{n,k}$ and Borsuk graphs of the $k$-sphere and use this together with calculations in the $\mathbb{Z}_2$-cohomology ring of $D_{2m}$ to tell which stable Kneser graphs are test graphs in the sense of Babson and Kozlov. The graphs $SG_{2s,4}$ are test graphs, i.e. for every graph $H$ and $r \geq 0$ such that $\mathrm{Hom}(SG_{2s,4},H)$ is $(r-1)$-connected, the chromatic number $\chi (H)$ is at least $r+6$. On the other hand, if $k \notin \{0,1,2,4,8\}$ and $n \geq N(k)$ then $SG_{n,k}$ is not a homotopy test graph, i.e. there are a graph $G$ and an $r \geq 1$ such that $\mathrm{Hom}(SG_{n,k}, G)$ is $(r-1)$-connected and $\chi (G) < r+k+2$. The latter result also depends on a new necessary criterion for being a test graph, which involves the automorphism group of the graph.