Geodesic
Topological obstructions to graph colorings
Babson, Eric1 ; Kozlov, Dmitry2, 3
1 Department of Mathematics, University of Washington, Seattle, Washington
2 Department of Mathematics, Royal Institute of Technology, Stockholm, Sweden
3 Department of Mathematics, University of Bern, Switzerland
Electronic research announcements of the American Mathematical Society, Tome 09 (2003), pp. 61-68 Cet article a éte moissonné depuis la source American Mathematical Society

Voir la notice de l'article

For any two graphs $G$ and $H$ Lovász has defined a cell complex $\mathtt {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 $\operatorname {Hom}(C_{2r+1},G)$ is $k$-connected, then $\chi (G)\geq k+4$. Our actual statement is somewhat sharper, as we find obstructions already in the nonvanishing of powers of certain Stiefel-Whitney classes.
DOI : 10.1090/S1079-6762-03-00112-4

Babson, Eric 1 ; Kozlov, Dmitry 2, 3

1 Department of Mathematics, University of Washington, Seattle, Washington
2 Department of Mathematics, Royal Institute of Technology, Stockholm, Sweden
3 Department of Mathematics, University of Bern, Switzerland 
@article{10_1090_S1079_6762_03_00112_4,
     author = {Babson, Eric and Kozlov, Dmitry},
     title = {Topological obstructions to graph colorings},
     journal = {Electronic research announcements of the American Mathematical Society},
     pages = {61--68},
     year = {2003},
     volume = {09},
     doi = {10.1090/S1079-6762-03-00112-4},
     url = {http://geodesic.mathdoc.fr/articles/10.1090/S1079-6762-03-00112-4/}
}
TY  - JOUR
AU  - Babson, Eric
AU  - Kozlov, Dmitry
TI  - Topological obstructions to graph colorings
JO  - Electronic research announcements of the American Mathematical Society
PY  - 2003
SP  - 61
EP  - 68
VL  - 09
UR  - http://geodesic.mathdoc.fr/articles/10.1090/S1079-6762-03-00112-4/
DO  - 10.1090/S1079-6762-03-00112-4
ID  - 10_1090_S1079_6762_03_00112_4
ER  - 
%0 Journal Article
%A Babson, Eric
%A Kozlov, Dmitry
%T Topological obstructions to graph colorings
%J Electronic research announcements of the American Mathematical Society
%D 2003
%P 61-68
%V 09
%U http://geodesic.mathdoc.fr/articles/10.1090/S1079-6762-03-00112-4/
%R 10.1090/S1079-6762-03-00112-4
%F 10_1090_S1079_6762_03_00112_4
Babson, Eric; Kozlov, Dmitry. Topological obstructions to graph colorings. Electronic research announcements of the American Mathematical Society, Tome 09 (2003), pp. 61-68. doi: 10.1090/S1079-6762-03-00112-4

[1] Lovász, L. Kneser’s conjecture, chromatic number, and homotopy J. Combin. Theory Ser. A 1978 319 324

[2] Quillen, Daniel Higher algebraic 𝐾-theory. I 1973 85 147

[3] Ziegler, Günter M. Generalized Kneser coloring theorems with combinatorial proofs Invent. Math. 2002 671 691

Cité par Sources :