The stable Kneser graph $SG_{ n,k}$, $n\ge1$, $k\ge0$, introduced by Schrijver \cite{ schrijver}, is a vertex critical graph with chromatic number $k+2$, its vertices are certain subsets of a set of cardinality $m=2n+k$. Bj\"orner and de Longueville \cite{ anders-mark} have shown that its box complex is homotopy equivalent to a sphere, $\Hom(K_2,SG_{ n,k})\homot\Sphere^k$. The dihedral group $D_{ 2m}$ acts canonically on $SG_{ n,k}$, the group $C_2$ with 2 elements acts on $K_2$. We almost determine the $(C_2\times D_{ 2m})$-homotopy type of $\Hom(K_2,SG_{ n,k})$ and use this to prove the following results. The graphs $SG_{ 2s,4}$ are homotopy test graphs, i.e. for every graph $H$ and $r\ge0$ such that $\Hom(SG_{ 2s,4},H)$ is $(r-1)$-connected, the chromatic number $\chi(H)$ is at least $r+6$. If $k\notin\set{ 0,1,2,4,8}$ and $n\ge N(k)$ then $SG_{ n,k}$ is not a homotopy test graph, i.e.\ there are a graph $G$ and an $r\ge1$ such that $\Hom(SG_{ n,k}, G)$ is $(r-1)$-connected and $\chi(G)<r+k+2$.

Categories: math.CO math.AT

The equivariant topology of stable Kneser graphs