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