Topological obstructions to graph colorings
| dc.creator | Babson, Eric | |
| dc.creator | Kozlov, Dmitry N. | |
| dc.date | 2003-05-21 | |
| dc.date | 2003-08-03 | |
| dc.date.accessioned | 2026-07-07T04:58:10Z | |
| dc.date.available | 2026-07-07T04:58:10Z | |
| dc.description | For any two graphs $G$ and $H$ Lovász has defined a cell complex $Hom(G,H)$ having in mind the general program that the algebraic invariants of these complexes should provide obstructions to graph colorings. Here we announce the proof of a conjecture of Lovász concerning these complexes with $G$ a cycle of odd length. More specifically, we show that: if $Hom(C_{2r+1},G)$ is $k$-connected, then $χ(G)\geq k+4$. Our actual statement is somewhat sharper, as we find obstructions already in the non-vanishing of powers of certain Stiefel-Whitney classes. | |
| dc.description | This is a research announcement, which is to appear in ERA-AMS | |
| dc.identifier | https://arxiv.org/abs/math/0305300 | |
| dc.identifier | http://arxiv.org/abs/math/0305300 | |
| dc.identifier | Electron. Res. Announc. Amer. Math. Soc. 9 (2003), 61--68 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/67527 | |
| dc.subject | Combinatorics | |
| dc.subject | Algebraic Topology | |
| dc.subject | 05C15; 57M15, 55N91, 55T99 | |
| dc.title | Topological obstructions to graph colorings | |
| dc.type | text |