A counterexample to a conjecture of Lov\'asz on the $\chi$-coloring complex
Shlomo Hoory, Nathan Linial · arXiv (Cornell University) · 2004
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 Bjorner and Lovasz, this graph $G'$ must be disconnected. In this note we give a counterexample to this conjecture.