A counterexample to a conjecture of Björner and Lovász on the χ-coloring complex

Associated with every graph G of chromatic number χ is another graph G′. The vertex set of G′ consists of all χ-colorings of G, and two χ-colorings are adjacent when they differ on exactly one vertex. According to a conjecture of Björner and Lovász, this graph G′ must be disconnected. In this note we give a counterexample to this conjecture.