Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, December 16, 2003, 12:15 pm

Duration: This information is not available in the database

Location: This information is not available in the database

Speaker: Péter Csorba

Coloring Graphs and Stiefel Manifolds?

In the topological approach to graph coloring problems, initiated by Lov\'asz, lower bounds on the chromatic number $\chi (G)$ of a graph $G$ are obtained by associating certain simplicial or cell complexes to $G$ and then exploiting topological invariants of the resulting spaces.

Recently, Babson and Kozlov proved Lov\'asz' conjecture that if for a graph $G$ the cell complex $Hom(C_{2r+1},G)$, introduced by Lov\'asz, is $k$-connected for some $r\geq 1$, then $\chi (G)\geq k+4$.

In this talk, we will see why is it difficult and that, in fact, $Hom(C_{5},K_{n+2})$ is an $({n-1})$-sphere bundle over the $n$-sphere.

(Joint work with Frank Lutz)

Information for students and suggested topics for student talks