Topological obstructions to graph colorings

被引：14

作者：

Babson, E ^{[1
]}

Kozlov, DN

机构：

[1] Univ Washington, Dept Math, Seattle, WA 98195 USA

[2] Royal Inst Technol, Dept Math, S-10044 Stockholm, Sweden

[3] Univ Bern, Dept Math, CH-3012 Bern, Switzerland

来源：

ELECTRONIC RESEARCH ANNOUNCEMENTS OF THE AMERICAN MATHEMATICAL SOCIETY | 2003年 / 9卷

关键词：

graphs; chromatic number; graph homomorphisms; Stiefel-Whitney classes; equivariant cohomology; free action; spectral sequences; obstructions; Kneser conjecture; Borsuk-Ulam theorem;

D O I：

10.1090/S1079-6762-03-00112-4

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

For any two graphs G and H Lovasz 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 Lovasz concerning these complexes with G a cycle of odd length. More specifically, we show that If Hom (C2r+1; G) is k- connected, then chi(G) greater than or equal to k + 4. Our actual statement is somewhat sharper, as we find obstructions already in the nonvanishing of powers of certain Stiefel-Whitney classes.

引用

页码：61 / 68

页数：8