A counterexample to a conjecture of Björner and Lovász on the $\ddot{I}‡$-coloring complex

Abstract

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

To appear in JCTB