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

Shlomo Hoory, Nathan Linial

Published 2004-05-17, updated 2005-05-17Version 2

Associated with every graph $G$ of chromatic number $\chi$ is another graph $G'$. The vertex set of $G'$ consists of all $\chi$-colorings of $G$, and two $\chi$-colorings are adjacent when they differ on exactly one vertex. According to a conjecture of Bj\"{o}rner and Lov\'asz, this graph $G'$ must be disconnected. In this note we give a counterexample to this conjecture.