A counterexample to a conjecture of Björner and Lovász on the $χ$-coloring complex
| dc.creator | Hoory, Shlomo | |
| dc.creator | Linial, Nathan | |
| dc.date | 2004-05-17 | |
| dc.date | 2005-05-17 | |
| dc.date.accessioned | 2026-07-07T05:08:22Z | |
| dc.date.available | 2026-07-07T05:08:22Z | |
| dc.description | 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. | |
| dc.description | To appear in JCTB | |
| dc.identifier | https://arxiv.org/abs/math/0405339 | |
| dc.identifier | http://arxiv.org/abs/math/0405339 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/71229 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C15; 05C40; 57M15 | |
| dc.title | A counterexample to a conjecture of Björner and Lovász on the $χ$-coloring complex | |
| dc.type | text |