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

Abstract

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.

To appear in JCTB