Higher connectivity of graph coloring complexes
| dc.creator | Cukic, Sonja Lj. | |
| dc.creator | Kozlov, Dmitry N. | |
| dc.date | 2004-10-14 | |
| dc.date | 2005-01-31 | |
| dc.date.accessioned | 2026-07-07T05:13:17Z | |
| dc.date.available | 2026-07-07T05:13:17Z | |
| dc.description | The main result of this paper is a proof of the following conjecture of Babson & Kozlov: Theorem. Let G be a graph of maximal valency d, then the complex Hom(G,K_n) is at least (n-d-2)-connected. Here Hom(-,-) denotes the polyhedral complex introduced by Lovász to study the topological lower bounds for chromatic numbers of graphs. We will also prove, as a corollary to the main theorem, that the complex Hom(C_{2r+1},K_n) is (n-4)-connected, for $n\geq 3$. | |
| dc.description | 16 pages, 6 figures | |
| dc.identifier | https://arxiv.org/abs/math/0410335 | |
| dc.identifier | http://arxiv.org/abs/math/0410335 | |
| dc.identifier | IMRN 2005:25 (2005) 1543-1562. | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/72888 | |
| dc.subject | Combinatorics | |
| dc.subject | Algebraic Topology | |
| dc.subject | 05C15; 57M15 | |
| dc.title | Higher connectivity of graph coloring complexes | |
| dc.type | text |