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.