Topological obstructions to graph colorings
Eric K. Babson, Dmitry N. Kozlov · Electronic Research Announcements of the American Mathematical Society · 2003
For any two graphs G G and H H Lovász has defined a cell complex H o m ( G , H ) \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 G a cycle of odd length. More specifically, we show that If Hom ( C 2 r + 1 , G ) \operatorname {Hom}(C_{2r+1},G) is k k -connected, then χ ( G ) ≥ k + 4 \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.