Topological obstructions to graph colorings

Details Topological obstructions to graph colorings Topological obstructions to graph colorings

2003-05-21

arxiv.org/abs/math/0305300v3

Electron. Res. Announc. Amer. Math. Soc. 9 (2003), 61--68

Mathematics

Combinatorics

This is a research announcement, which is to appear in ERA-AMS

Scientific paper

For any two graphs $G$ and $H$ Lov\'asz 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\'asz 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 $\chi(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.

Affiliated with

Also associated with

No associations

Rating

Topological obstructions to graph colorings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Topological obstructions to graph colorings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Topological obstructions to graph colorings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-343790