Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, June 09, 2009, 12:15 pm
Duration: This information is not available in the database
Location: OAT S15/S16/S17
Speaker: Jan Foniok
A theorem attributed to Hasse, Gallai, Roy and/or Vitaver claims that every orientation of every non-k-colourable graph contains a long directed path or a directed cycle (so it contains a homomorphic image of a long directed path), where "long" means "with at least k+1 vertices". We extend this theorem and prove that there is a family P of oriented paths with unbounded algebraic height such that every orientation of every non-4-colourable graph contains a homomorphic image of every path in P. (algebraic height = #forward arcs - #backward arcs) The motivation for this work is Hedetniemi's product- colouring conjecture (but probably I will not have time to discuss it); the method is "adjoint functors" (and I certainly want to discuss that).
Joint work with J. Nešetřil and C. Tardif.
Automatic MiSe System Software Version 1.4803M | admin login