Geodesic
Topological obstructions to graph colorings
Babson, Eric1 ; Kozlov, Dmitry2, 3
1Department of Mathematics, University of Washington, Seattle, Washington
2Department of Mathematics, Royal Institute of Technology, Stockholm, Sweden
3Department 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 :