Paths of homomorphisms from stable Kneser graphs (Q485504)

The Kneser graph \(\mathrm{KG}_{n,k}\) has as vertices the \(k\)-element subsets of an \(n\)-set with two vertices adjacent if and only if the two corresponding sets are disjoint. The stable Kneser graph, also known as the Schrijver graph \(\mathrm{SG}_{n,k}\), is the subgraph of \(\mathrm{KG}_{n,k}\) induced by all \(k\)-subsets of \([n]\) that do not contain two consecutive numbers in the cyclic ordering of \([n]\). The graph \(\mathrm{SG}_{n,k}\) has chromatic number \(k+2\) but every proper subgraph has chromatic number at most \(k+1\). The complex \(\text{Hom}(G,H)\) has vertices all graph homomorphisms from \(G\) to \(H\) and whose topology captures global properties of these homomorphisms. A graph \(T\) is a test graph if for all graphs \(G\) and \(r \geq 0\), \(\text{Hom}(T,G)\) is \((r-1)\)-connected implies that \(\chi(G) \geq r+\chi(T)\). The author shows that for \(k \equiv 3 \pmod{4}\) and \(n \geq 2\) there is a component of the \(\chi\)-coloring graph of \(\mathrm{SG}_{n,k}\) that is invariant under the action of the automorphism group of \(\mathrm{SG}_{n,k}\). He derives that there is a graph \(G\) with \(\chi(G) = \chi(\mathrm{SG}_{n,k})\) such that \(\text{Hom}(\mathrm{SG}_{n,k},G)\) is nonempty and connected. In particular, for these \(n\) and \(k\), the graph \(\mathrm{SG}_{n,k}\) is not a test graph.