A counterexample to a conjecture of Björner and Lovász on the \(\chi\)-coloring complex. (English) Zbl 1075.05036
Summary: 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örner and Lovász, this graph \(G'\) must be disconnected. In this note we give a counterexample to this conjecture.
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
Keywords:
chromatic numberReferences:
| [1] | E. Babson, D. Kozlov, Complexes of graph homomorphisms, http://arxiv.org/abs/math.CO/0310056; E. Babson, D. Kozlov, Complexes of graph homomorphisms, http://arxiv.org/abs/math.CO/0310056 · Zbl 1205.52009 |
| [2] | E. Babson, D. Kozlov, Proof of the Lovász conjecture, http://arxiv.org/abs/math.CO/0402395; E. Babson, D. Kozlov, Proof of the Lovász conjecture, http://arxiv.org/abs/math.CO/0402395 |
| [3] | Lovász, L., Kneser’s conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A, 25, 3, 319-324 (1978) · Zbl 0418.05028 |
| [4] | J. Matoušek, Lectures on topological methods in combinatorics and geometry, Written in cooperation with Anders Björner and Günter M. Ziegler, Using the Borsuk-Ulam Theorem, Universitext, Springer, Berlin, 2003.; J. Matoušek, Lectures on topological methods in combinatorics and geometry, Written in cooperation with Anders Björner and Günter M. Ziegler, Using the Borsuk-Ulam Theorem, Universitext, Springer, Berlin, 2003. · Zbl 1016.05001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
