Article ID Journal Published Year Pages File Type
9515910 Journal of Combinatorial Theory, Series B 2005 4 Pages PDF
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.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,